Min Stack

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with $O(1)$ time complexity for each function.

Example 1:
Input:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output:
[null,null,null,null,-3,null,0,-2]

Explanation:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Approach: Two Stacks

To achieve $O(1)$ time complexity for all operations, including getMin(), we can use two stacks:

1. stack: This will act as our standard stack to store the actual elements.
2. minStack: This will keep track of the minimum value present in the stack at any given level.

Whenever we push an element onto stack, we check if it is smaller than or equal to the current minimum (which is the top element of minStack). If it is, we push it onto minStack. If it’s not, we simply only push to minStack when the new value is $\le$ the current minimum (to optimize space).

1. push(val): Push val to stack. If minStack is empty or val $\le$ the top of minStack, push val to minStack.
2. pop(): Pop the top element from stack. If this popped element is equal to the top of minStack, it means we are removing the current minimum, so we must also pop from minStack.
3. top(): Return the top element of stack.
4. getMin(): Return the top element of minStack.

Solution

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

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push(val);
    
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(val);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    const popped = this.stack.pop();
    
    if (popped === 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];
};

Complexity Analysis

• Time Complexity: $O(1)$ for all operations (push, pop, top, getMin). We only perform basic array push/pop and array indexing operations, all of which run in constant time.
• Space Complexity: $O(n)$ where $n$ is the number of operations performed. In the worst case, every element pushed could be a new minimum (e.g., pushing elements in strictly descending order), meaning both stack and minStack will store $n$ elements.