Course4all
Join us on telegram
Home/dsa/Stack/Min Stack

Min Stack

Master this topic with zero to advance depth.

Min Stack

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

Visual Representation

Push: -2, 0, -3 Stack: MinStack: | -3 | | -3 | | 0 | | -2 | | -2 | | -2 | +----+ +----+ getMin() -> -3 pop() top() -> 0 getMin() -> -2
Easy

Examples

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]\n[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Approach 1

Level I: Single Stack (Brute Force Min)

Intuition

Use a standard stack for push, pop, and top. For getMin(), iterate over the entire stack to find the minimum value. This saves space over a two-stack approach but sacrifices the constant-time operation for querying the minimum.

⏱ O(1) for push/pop/top. O(N) for getMin.💾 O(N) for the underlying stack.
java
import java.util.*;

class MinStack {
    private List<Integer> s = new ArrayList<>();
    public void push(int val) { s.add(val); }
    public void pop() { s.remove(s.size() - 1); }
    public int top() { return s.get(s.size() - 1); }
    public int getMin() {
        int mn = Integer.MAX_VALUE;
        for (int n : s) if (n < mn) mn = n;
        return mn;
    }
}
Approach 2

Level II: Single Stack (Value-Min Pairs)

Intuition

Instead of two separate stacks, we can store pairs on a single stack. Each entry on the stack will be (current_value, current_min_so_far). This is conceptually simpler and ensures the value and its corresponding minimum are always synchronized.

⏱ O(1) for all operations.💾 O(N) to store pairs.
java
import java.util.Stack;

class MinStack {
    private Stack<int[]> stack = new Stack<>();
    
    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(new int[]{val, val});
        } else {
            stack.push(new int[]{val, Math.min(val, stack.peek()[1])});
        }
    }
    
    public void pop() { stack.pop(); }
    public int top() { return stack.peek()[0]; }
    public int getMin() { return stack.peek()[1]; }
}
Approach 3

Level III: Optimal (Two Stacks)

Intuition

Maintain two stacks: one for all elements and another to keep track of the minimum at each state. When pushing a value, if it is less than or equal to the current minimum, push it onto the min stack as well. This ensures O(1) retrieval.

⏱ O(1) for all operations.💾 O(N)

Detailed Dry Run

OperationValueStackMinStackOutput
push-2[-2][-2]-
push0[-2, 0][-2]-
push-3[-2, 0, -3][-2, -3]-
getMin----3
pop-[-2, 0][-2]-
java
import java.util.Stack;

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) minStack.push(val);
    }
    
    public void pop() {
        if (stack.pop().equals(minStack.peek())) minStack.pop();
    }
    
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
    
    public static void main(String[] args) {
        MinStack ms = new MinStack();
        ms.push(-2); ms.push(0); ms.push(-3);
        System.out.println(ms.getMin()); // -3
        ms.pop();
        System.out.println(ms.top());    // 0
        System.out.println(ms.getMin()); // -2
    }
}

⚠️ Common Pitfalls & Tips

In Java, use .equals() instead of == for Stack comparisons as Integer objects might be outside the cache range.

← Previous QuestionValid Parentheses
Next Question →Implement Queue using Stacks