22.Min Stack

MediumStack · 2/7

Problem

Design a stack that supports the usual operations and can return the minimum element — all in O(1) time.

Implement the MinStack class:

MinStack() initialises the stack.
void push(int val) pushes val onto the stack.
void pop() removes the top element.
int top() returns the top element.
int getMin() returns the smallest element currently in the stack.

Examples

Input:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output:
[null,null,null,null,-3,null,0,-2]
Explanation:
  push(-2), push(0), push(-3)  → stack [-2, 0, -3]
  getMin() → -3
  pop()                        → stack [-2, 0]
  top()    → 0
  getMin() → -2

Input:
["MinStack","push","push","getMin","pop","getMin"]
[[],[1],[1],[],[],[]]
Output:
[null,null,null,1,null,1]
Explanation: Duplicated minimums must survive a single pop.

Constraints

-2^31 <= val <= 2^31 - 1
pop, top and getMin are always called on a non-empty stack.
At most 3 * 10^4 calls in total.

💡 Key Insight

A stack only changes at its top, so the minimum of the stack below any element never changes while that element is present. Therefore we can record, at push time, "what is the minimum once this element is on the stack?" — and popping simply restores the previous record. No re-scanning is ever needed.

Brute Force (Scan for Minimum)

TimeO(1) for push, pop, top; **O(n)** for getMinSpaceO(n)

Intuition

Store elements in a list; push, pop and top work at the end of the list. For getMin, scan every element.

Algorithm

push: append to the list.
pop: remove the last element.
top: return the last element.
getMin: iterate the whole list and return the smallest value.

Visualization

list = [-2, 0, -3]
getMin → scan -2, 0, -3 → -3     (O(n) every call)

Code

java

import java.util.ArrayList;
import java.util.List;

class MinStack {
    private final List<Integer> data = new ArrayList<>();

    public MinStack() {
    }

    public void push(int val) {
        data.add(val);
    }

    public void pop() {
        data.remove(data.size() - 1);
    }

    public int top() {
        return data.get(data.size() - 1);
    }

    public int getMin() {
        int min = Integer.MAX_VALUE;
        for (int value : data) {
            min = Math.min(min, value); // full scan each time
        }
        return min;
    }
}

Complexity

Time: O(1) for push, pop, top; O(n) for getMin — violates the requirement.
Space: O(n) — the stored elements.

Stack of (value, minSoFar) Pairs

TimeO(1) for every operation.SpaceO(n)

Intuition

Using the key insight, store each element together with the minimum of the stack including it. The top pair then always carries the current minimum, and popping automatically reveals the previous minimum.

Algorithm

push(val): newMin = isEmpty ? val : min(val, top.min); push {val, newMin}.
pop(): pop the top pair.
top(): return top.value.
getMin(): return top.min.

Dry Run

push(-2) → [(-2,-2)]
push(0)  → [(-2,-2), (0,-2)]
push(-3) → [(-2,-2), (0,-2), (-3,-3)]   getMin = -3
pop()    → [(-2,-2), (0,-2)]            top = 0, getMin = -2

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    // each entry: {value, minimum of the stack up to and including this entry}
    private final Deque<int[]> stack = new ArrayDeque<>();

    public MinStack() {
    }

    public void push(int val) {
        int newMin = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[] {val, newMin});
    }

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

    public int top() {
        return stack.peek()[0];
    }

    public int getMin() {
        return stack.peek()[1];
    }
}

Complexity

Time: O(1) for every operation.
Space: O(n) — two ints per element.

Two Stacks with a Lazy Min StackOptimal

TimeO(1) for every operation.SpaceO(n) worst case (strictly decreasing pushes), usually less than the pair approach.

Intuition

The pair approach stores a minimum for every element, even when it repeats the same value. Instead keep a second stack minStack that only receives a value when it is a new minimum or equal to the current one (val <= minStack.peek()). On pop, if the removed value equals minStack.peek(), pop that too. Still O(1) everywhere, and in typical inputs the min stack is much smaller.

Algorithm

push(val): push onto stack; if minStack is empty or val <= minStack.peek(), push onto minStack.
pop(): removed = stack.pop(); if removed == minStack.peek(), pop minStack.
top(): stack.peek().
getMin(): minStack.peek().

Dry Run

flowchart TD
    A["push -2<br/>stack [-2], min [-2]"] --> B["push 0 (0 > -2)<br/>stack [-2, 0], min [-2]"]
    B --> C["push -3 (-3 <= -2)<br/>stack [-2, 0, -3], min [-2, -3]"]
    C --> D["getMin → -3"]
    D --> E["pop -3 (equals min top)<br/>stack [-2, 0], min [-2]"]
    E --> F["top → 0, getMin → -2"]

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> minStack = new ArrayDeque<>(); // non-increasing minima

    public MinStack() {
    }

    public void push(int val) {
        stack.push(val);
        // use <= so duplicate minimums are tracked separately
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        int removed = stack.pop();
        // compare as int, not Integer references
        if (removed == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

Complexity

Time: O(1) for every operation.
Space: O(n) worst case (strictly decreasing pushes), usually less than the pair approach.

Complexity Comparison

Approach	Time (getMin)	Space
Brute Force (scan)	O(n)	O(n)
Stack of pairs	O(1)	O(n)
Two stacks (lazy min)	O(1)	O(n)

Common Pitfalls

Pushing to the min stack only when val < min (strict) — after push(1), push(1), pop() the min stack would be empty even though 1 is still on the stack.
Comparing stack.pop() == minStack.peek() directly: both are Integer, so == compares references and fails for values outside [-128, 127]. Unbox one side into an int first.
Keeping a single min variable — after popping the minimum you have no way to recover the previous one.
Using Integer.MAX_VALUE as a sentinel and then mishandling a real pushed value of Integer.MAX_VALUE.