🌱 Keegan's Digital Garden

155. Min Stack

3 min read

📝 Problem Details

🔍 Problem Understanding

Design a class for a stack data structure that supports the following operations:

  • 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.

Constraint: each function cannot exceed a time complexity of O(1)

🎯 Key Insights

- the challenge of this problem lies in the `getMin()` function, as this is something that is fundamentally in conflict with the way a traditional stack data structure operates

- elements should be placed in the stack, in order of insertion, but we also need a way to keep track of the minimum element inside that stack at any given time
	- a brute force (unacceptable) approach could be to convert the stack into a vector, sort it, and return the first element
	- the above approach would be O(n log n) in time and O(n) additional space

🔑 Approach

1. Use an auxiliary stack to keep track of the minimum element at every step.
2. For each operation:
   - **Push:** Push the value onto the main stack. If the auxiliary stack is empty or the new value is smaller than or equal to the current minimum, push it onto the auxiliary stack as well.
   - **Pop:** Remove the top value from the main stack. If the popped value is equal to the top of the auxiliary stack, remove it from the auxiliary stack as well.
   - **Top:** Return the top element of the main stack.
   - **GetMin:** Return the top element of the auxiliary stack.
3. This approach ensures that we always have the current minimum at the top of the auxiliary stack, allowing O(1) access time for `getMin()`.

💡 Explanation of Solution

- A single stack alone cannot efficiently retrieve the minimum element in O(1) time, so we use an auxiliary stack.
- The auxiliary stack stores the minimum element at each stage:
  - When a new minimum element is pushed, it is added to the auxiliary stack.
  - When the current minimum element is popped from the main stack, the corresponding minimum is also popped from the auxiliary stack.
- The auxiliary stack grows and shrinks in sync with the main stack but only stores the minimum values.
- This ensures efficient O(1) operations for all stack methods, including `getMin()`.

⌛ Complexity Analysis

Time Complexity: 
O(1) for all operations (`push`, `pop`, `top`, `getMin`), as each operation involves a constant amount of work.

Space Complexity:
O(n), where n is the number of elements in the stack. The auxiliary stack stores the minimum values, which, in the worst case, is proportional to the size of the main stack.

💻 Implementation of Solution

class MinStack {
private:
    stack<int> stk;
    stack<int> min;
 
public:
    MinStack() {
        
    }
    
    void push(int val) {
        stk.push(val);
 
        if(min.empty() || val <= min.top()){
            min.push(val);
        }    
    }
    
    void pop() {
        if(min.top() == stk.top())
            min.pop();
        stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return min.top();
    }
};

Graph View