LeetCode 155 · Medium · Stack

Min Stack

Design a stack that supports push, pop, top and getMin (the smallest value currently in the stack), each in constant time.

O(1)every call
O(n)space
2 stacksmin per height

push x, pop, top, getMin · comma-separated · 1–16 calls · x from −99 to 99 · pop/top/getMin need a non-empty stack

Calls pointer walks the calls · return value underneath

stackvalues

minStackmin at or below each height

class MinStack { // min at or below each level private Deque<Integer> stack; private Deque<Integer> minStack; public MinStack() { stack = new ArrayDeque<>(); minStack = new ArrayDeque<>(); } public void push(int val) { stack.push(val); if (!minStack.isEmpty()) { val = Math.min(val, minStack.peek()); } minStack.push(val); } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); }}
call
—
val
—
stack
[]
minStack
[]
output
[]

Why it works

  1. Brute force scans: getMin runs Collections.min(stack), O(n) per call. Keeping one "current min" variable is not enough either: once that value is popped, finding the next min means a rescan.
  2. Key invariant: minStack at height h is the minimum of the h lowest values of stack. A stack only changes at the top, so everything below height h stays put, and so does its minimum. Store it once per height.
  3. Every call is O(1). push needs only val and the level below; pop drops both tops and the level below is already right; getMin reads one cell. Space is O(n), one min per value.
  4. Pitfall: duplicate minimums. The space-saving variant only pushes to minStack when val <= minStack.peek(). Write < instead and push 0, 1, 0 then pop loses the remaining 0. The per-height version here stores every level, so ties are safe. In that variant compare the popped value with .equals, not ==: boxed Integers outside −128..127 are different objects.
  5. Same idea, one stack: push pairs {val, minSoFar} (an int[]). Or keep a single min and store val − min, decoding on pop, for O(1) extra space.
  6. Follow-up: Max Stack (716) needs popMax too, so it moves to a TreeMap or two heaps. A min or max over a sliding window uses a monotonic ArrayDeque (239).