Building an Efficient MinStack in JavaScript🚀

In the world of computer science and programming, data structures play a pivotal role in solving complex problems efficiently. One such problem is designing a specialized stack known as the MinStack. This stack not only supports standard push and pop operations but also provides constant-time access to the minimum element within the stack. In this blog, we'll explore a clever implementation of the MinStack in JavaScript that meets the stringent O(1) time complexity requirements for each function.
Leetcode Question

Understanding the Problem

The problem statement calls for the design of a MinStack that supports the following operations:

push(val): Adds an element to the top of the stack.
pop(): Removes the element from the top of the stack.
top(): Returns the element at the top of the stack.
getMin(): Retrieves the minimum element in the stack.

The key challenge here is to maintain the minimum element efficiently while performing all these operations in constant time O(1).

The MinStack Implementation

To implement the MinStack, we can make use of two separate stacks:

The main stack: This stack holds all the elements in the order they were pushed onto the stack.
The minimum stack: This stack keeps track of the minimum elements encountered at each step.
Let's break down the implementation step by step:

Initialization

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }
}

We initialize two empty arrays, stack and minStack, to hold our data.

Push Operation

push(val) {
    // If the minStack is empty or the new value is smaller than or equal to the current minimum,
    // push the new value onto the minStack.
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(val);
    }
    // Push the new value onto the main stack.
    this.stack.push(val);
}

When pushing a new value onto the stack, we compare it with the current minimum stored in the minStack. If the new value is smaller than or equal to the current minimum, we also push it onto the minStack. This ensures that we always have the correct minimum value at the top of the minStack.

Pop Operation

pop() {
    // Retrieve the top elements from both stacks.
    const stackTop = this.stack.pop();
    const minStackTop = this.minStack[this.minStack.length - 1];

    // If the top elements are equal, pop from the minStack as well.
    if (stackTop === minStackTop) {
        this.minStack.pop();
    }
}

When popping an element from the main stack, we compare it with the top element of the minStack. If they are equal, it means the minimum element is being removed, so we also pop from the minStack.

Top (Peek) Operation

top() {
    return this.stack[this.stack.length - 1];
}

The top() function simply returns the element at the top of the stack.

GetMin Operation

getMin() {
    return this.minStack[this.minStack.length - 1];
}

The getMin() function returns the top element of the minStack, which is the minimum value in the stack at any given point.

Conclusion

In this blog post, we explored the concept of the MinStack, a specialized stack that efficiently supports operations such as push, pop, top, and retrieving the minimum element, all in constant time. By employing two separate stacks, the main stack and the minimum stack, we can maintain the minimum element while performing other operations without sacrificing efficiency. This elegant solution showcases how clever data structure design can lead to remarkable performance improvements in solving real-world problems.

Connect with me on my:

LinkedIn
GitHub
Twitter