Pattern visualizer

Min Stack

Store each element alongside the minimum seen so far at that point in the stack: (value, minSoFar). Pushing recomputes minSoFar as min(newValue, previous top's minSoFar); popping simply reveals the minSoFar already stored one level down. getMin() becomes a plain O(1) read of the top pair. Animated on: Design a stack that supports push, pop, top, and getMin in O(1). Use a pair-stack where each element stores (value, minSoFar)..

Stack

step 1 / 8

line 1

Step 1: Initialize empty MinStack. Stack is empty. No elements to point to.

Pseudocode

1MinStack: keep a stack whose items are pairs (value, minSoFar)
2push(val):
3  minSoFar = val if the stack is empty, otherwise the smaller of val and the top pair's minSoFar
4  push the pair (val, minSoFar) onto the stack
5end push
6pop(): remove the top pair from the stack
7top(): return the value of the top pair
8getMin(): return the minSoFar of the top pair

← / → step · space play · Home restart

Where to practice Stack

Practice Stack problems All Stack problems Back to roadmap