Command Palette

Search for a command to run...

Hectal
Problem 9.2 · Stack and Monotonic StackMedium

Min Stack

PatternCombine Structures to DesignStack for Matching and Undo

What it teaches: Store extra state with each element (the minimum so far) so every query stays O(1).

Practise it on judges as “Min Stack”.

The problem

Design a stack that supports push(val), pop(), top() and getMin() (the smallest element in the stack), each in O(1) time.

Tests call the methods in order: ops lists the calls and args their arguments; the first call creates the object.

Example 1

Input: ops = [MinStack, push, push, push, getMin, pop, top, getMin]
args = [[], [-2], [0], [-3], [], [], [], []]
Output: [null, null, null, null, -3, null, 0, -2]

Constraints

  • −2³¹ ≤ val ≤ 2³¹ − 1
  • pop, top, getMin are only called on a non-empty stack
  • Up to 3 × 10⁴ calls

Pattern clues in the wording

  • → "Design" with O(1) for every operation
  • → The minimum must survive pops

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

MinStack.java · starter
import java.util.*;

class MinStack {
    public MinStack() {}
    public void push(int val) {}
    public void pop() {}
    public int top() { return 0; }
    public int getMin() { return 0; }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
ops = ["MinStack","push","push","push","getMin","pop","top","getMin"]
args = [[],[-2],[0],[-3],[],[],[],[]]
[null,null,null,null,-3,null,0,-2]
2
ops = ["MinStack","push","push","getMin","pop","getMin"]
args = [[],[1],[1],[],[],[]]
Duplicate minimums
[null,null,null,1,null,1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: pairs of (value, min so far) · O(1) per operation
1

Optimal: pairs of (value, min so far)

Time O(1) per operation Space O(n)

Push [val, min(val, currentMin)]. The top pair always carries the minimum of everything below and including it, so popping restores the previous minimum automatically.

▶ Dry run: Each entry remembers the minimumpush -2, push 0, push -3, getMin, pop, top, getMin

stack (value, min)(stack)

(-2, -2)

Step 1/4push −2: min so far −2.

Approach 1
import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();   // {value, min so far}

    public MinStack() {}

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

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

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

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

Verdict: Every operation is a single stack action.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Pushing duplicates of the minimum
  • Popping the minimum
  • Negative and extreme values

Mistakes people make

  • Keeping only one min variable: after popping the minimum you can't recover the previous one.
  • With two stacks, pushing to the min stack only when val < min (should be <=, or duplicates break).

Interview

Follow-up questions

Can you use less memory than a pair per element?