Min Stack

Medium#155value + minimum

Build a stack with push, pop and top that also answers getMin, the smallest value in it, and every call has to take O(1) time. pop, top and getMin are only called on a stack that is not empty. Our example: push(5), push(3), push(7), push(3), getMin(), pop(), getMin(), pop(), pop(), getMin(), top(). The four answers are 3, 3, 5 and 5.

155 Min StackWalkthrough · 1×

Example: push(5), push(3), push(7), push(3), getMin(), pop(), getMin(), pop(), pop(), getMin(), top(). Each column is one entry: its value on top, below it low, the minimum of that entry and all entries under it.

callMinStack()valuelow—returned—
on the stackjust pushed; low read by pushremoved by popwhat the call returns

MinStack() is created: init runs once

01/35
restart · back · play · step
Speed
1class MinStack:
2 function init():
3 stack = empty stack of pairs (value, low)
4 function push(x):
5 low = x
6 if stack is not empty:
7 low = min(x, stack.last.low)
8 push (x, low) onto stack
9 function pop():
10 remove stack.last
11 function top():
12 return stack.last.value
13 function getMin():
14 return stack.last.low
state
stack
–
x
–
low
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The entries under an entry never change while it is on the stack: they can only change after it is popped. So the low written when it was pushed stays right for as long as it stays.
  2. The low of a new entry is the smaller of its value and the low just below it, so getMin is the top's low: one lookup.
  3. A pop takes its low away with it, and the entry below already holds the minimum without it. That is why one minimum variable is not enough and a repeated minimum needs no counting.

Complexity

Time O(1) for every call: each one reads or changes only the top. Memory O(n) for n entries, two numbers each.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.