Min Stack

---

Min Stack: 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

---

Constraints:

• -2^31 <= val <= 2^31 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

---

Try this Problem on your own or check similar problems:

1. Sliding Window Maximum

Solution:

Java

class MinStack {
    private class ValueMinPair{
        int value, min;
        public ValueMinPair(int value, int min){
            this.value = value;
            this.min = min;
        }
    }
    Stack<ValueMinPair> s;
    public MinStack() {
        s = new Stack<>();
    }

    public void push(int val) {
        if(s.empty()) s.push(new ValueMinPair(val, val));
        else s.push(new ValueMinPair(val, Math.min(val, getMin())));
    }

    public void pop() {
        s.pop();
    }

    public int top() {
        return s.peek().value;
    }

    public int getMin() {
        return s.peek().min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

JavaScript

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

/**
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
  const min = this.stack.length === 0 ? val : Math.min(val, this.getMin());
  this.stack.push({ value: val, min });
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  this.stack.pop();
};

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

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

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

Python

class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        min_val = val if len(self.stack) == 0 else min(val, self.getMin())
        self.stack.append({"value": val, "min": min_val})

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]["value"]

    def getMin(self) -> int:
        return self.stack[-1]["min"]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

C++

class MinStack {
private:
    struct ValueMinPair {
        int value, min;
        ValueMinPair(int value, int min) : value(value), min(min) {}
    };
    stack<ValueMinPair> s;
public:
    MinStack() {

    }

    void push(int val) {
        if (s.empty())
            s.push(ValueMinPair(val, val));
        else
            s.push(ValueMinPair(val, min(val, getMin())));
    }

    void pop() {
        s.pop();
    }

    int top() {
        return s.top().value;
    }

    int getMin() {
        return s.top().min;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

---

Time/Space Complexity:

• Time Complexity: O(1)
• Space Complexity: O(n)

---

Explanation:

We have linear time complexity since we utilize stack to implement the class functionalities, but constant time complexity for each operation. The only trick to the problem is how to rapidly return the minimum value, since all other methods are natively supported by stack. To achieve this instead of just pushing the value to the stack we push a pair containing the value and also the minimum which is either the current value or the one of the previous values we have pushed to the stack. This enables us to retrieve the minimum just by reading the top pair and retrieving the min field.