Min Stack

Easystackdesign
Category: Stack
Companies that ask this question:
AmazonGoogleFacebookBloomberg
LeetCode →

Approach

Min Stack

Approach

Use two stacks - one for values, one for tracking minimum.

Algorithm

  1. Push: Add to main stack, add to min stack if new minimum
  2. Pop: Remove from main stack, remove from min stack if it was minimum
  3. Top: Peek at main stack
  4. GetMin: Peek at min stack

Complexity

  • Time: O(1) for all operations
  • Space: O(n) - two stacks

Key Insights

  • Min stack only stores values when they become new minimum
  • Allows O(1) minimum retrieval
  • Both stacks stay synchronized

Solution

java
1class MinStack {
2    private Stack<Integer> stack;
3    private Stack<Integer> minStack;
4    
5    public MinStack() {
6        stack = new Stack<>();
7        minStack = new Stack<>();
8    }
9    
10    public void push(int val) {
11        stack.push(val);
12        if (minStack.isEmpty() || val <= minStack.peek()) {
13            minStack.push(val);
14        }
15    }
16    
17    public void pop() {
18        int val = stack.pop();
19        if (val == minStack.peek()) {
20            minStack.pop();
21        }
22    }
23    
24    public int top() {
25        return stack.peek();
26    }
27    
28    public int getMin() {
29        return minStack.peek();
30    }
31}
Loading visualizer...