Min Stack medium

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 top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

Constraints:

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

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

Example 2

Input: ["MinStack","push","push","getMin","pop","getMin"] [[],[-2],[0],[],[],[]]

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

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

Steps

1. Data Structure: Use two stacks: dataStack to store the actual data and minStack to store the minimum values encountered so far.

2. push(val): Push val onto dataStack. If minStack is empty or val is less than or equal to the top of minStack, push val onto minStack.

3. pop(): Pop the top element from dataStack. If the popped element is equal to the top of minStack, pop the top element from minStack as well.

4. top(): Return the top element of dataStack.

5. getMin(): Return the top element of minStack.

Explanation

The key to achieving constant time complexity for getMin is using the minStack. minStack maintains a monotonically decreasing sequence of minimum values seen so far. This ensures that getMin only needs to access the top of minStack. Whenever we push a new element, we only push it to minStack if it's smaller than or equal to the current minimum. When we pop, we only remove from minStack if the popped element was the current minimum. This maintains the invariant that the top of minStack is always the minimum element in dataStack.

Code

#include <stack>

class MinStack {
private:
    stack<int> dataStack;
    stack<int> minStack;

public:
    MinStack() {}

    void push(int val) {
        dataStack.push(val);
        if (minStack.empty() || val <= minStack.top()) {
            minStack.push(val);
        }
    }

    void pop() {
        if (dataStack.top() == minStack.top()) {
            minStack.pop();
        }
        dataStack.pop();
    }

    int top() {
        return dataStack.top();
    }

    int getMin() {
        return minStack.top();
    }
};

Complexity

• Time Complexity:

  • push(): O(1)
  • pop(): O(1)
  • top(): O(1)
  • getMin(): O(1)

• Space Complexity: O(N), where N is the number of elements in the stack. We use two stacks to store the data, so the space used is proportional to the number of elements.