Implementing a MinStack in JavaScript

In this blog post, we will explore how to implement a MinStack in JavaScript, a useful data structure that supports standard stack operations and allows constant-time retrieval of the minimum element in the stack. A MinStack is particularly helpful when you need a way to track the minimum value dynamically as elements are added or removed.

What is a MinStack?

A stack is a basic data structure that follows the Last In, First Out (LIFO) principle. It supports the following operations:

• push(x): Add element x to the top of the stack.
• pop(): Remove the top element from the stack.
• top(): Retrieve the top element of the stack without removing it.
• getMin(): Retrieve the minimum element from the stack in constant time.

The challenge lies in implementing getMin() efficiently. Without additional optimizations, we might need to traverse the stack to find the minimum element, which could take linear time. A MinStack solves this problem by keeping track of the minimum element dynamically using an auxiliary stack (minStack) that tracks the minimum values.

How to Implement a MinStack

Step-by-Step Explanation

We’ll maintain two stacks:

1. stack: The main stack to store elements.
2. minStack: A secondary stack to keep track of the minimum values.

The logic is simple:

• Whenever we push a value to the main stack, we also push it to the minStack if it is smaller than or equal to the current minimum.
• When we pop from the main stack, we also pop from the minStack if the value being removed is the current minimum.
• This allows us to always have the minimum value on top of the minStack, so retrieving the minimum is efficient.

Here’s the complete implementation of the MinStack:

var MinStack = function() {
    this.stack = [];
    this.minStack = [];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    // If minStack is empty or x is less than or equal to the current minimum, push x onto minStack
    if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    const poppedValue = this.stack.pop();
    // If the popped value is equal to the top of the minStack, pop from minStack too
    if (poppedValue === this.minStack[this.minStack.length - 1]) {
        this.minStack.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1];
};

Breakdown of Operations

1. Push OperationMinStack.prototype.push = function(x) { this.stack.push(x); if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) { this.minStack.push(x); } };
   • We push the value onto the main stack.
   • If the minStack is empty or the value is less than or equal to the current minimum, we push the value onto the minStack as well.
2. Pop OperationMinStack.prototype.pop = function() { const poppedValue = this.stack.pop(); if (poppedValue === this.minStack[this.minStack.length - 1]) { this.minStack.pop(); } };
   • We remove the top value from the main stack.
   • If the popped value is the current minimum (i.e., it matches the top of the minStack), we remove it from the minStack too.
3. Top OperationMinStack.prototype.top = function() { return this.stack[this.stack.length - 1]; };
   • This function retrieves the top value of the stack without removing it.
4. GetMin Operation
   javascript MinStack.prototype.getMin = function() { return this.minStack[this.minStack.length - 1]; };
   • The minimum value is always at the top of the minStack. This ensures that we can retrieve the minimum element in constant time.

Example

let minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
console.log(minStack.getMin());  // Output: -3
minStack.pop();
console.log(minStack.top());     // Output: 0
console.log(minStack.getMin());  // Output: -2

In the above example:

1. We push three values onto the stack: -2, 0, and -3. Since -3 is the smallest value, getMin() returns -3.
2. After popping the top element (-3), the next minimum value is -2, which is retrieved using getMin() again.

Conclusion

A MinStack is a clever and efficient way to maintain a stack while being able to retrieve the minimum value in constant time. By using an auxiliary stack to track minimums, we ensure that the getMin() operation is fast, without compromising the performance of the standard stack operations like push, pop, and top.

This implementation is especially useful in algorithms where you frequently need the minimum value while modifying the stack, such as in range queries, sliding windows, or dynamic programming problems.