155. Min Stack — DSA Atlas

155

MediumStack and Expression ProcessingStackStack augmented with running minimum

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time. Implement MinStack with push(val), pop(), top() returning the top element, and getMin() returning the smallest element currently in the stack.

Open official problem prompt ↗

In plain English

Support all four stack operations, including reading the current minimum, in constant time.

Picture it like this

A stack of sticky notes where each note also records the smallest number written on any note from it downward, so the top note always tells you the overall minimum.

Example

Input: ops = ["MinStack","push","push","push","getMin","pop","top","getMin"], args = [[],[-2],[0],[-3],[],[],[],[]]
Output: [null, null, null, null, -3, null, 0, -2]
Why: After pushing -2, 0, -3 the min is -3; popping -3 leaves top 0 and min -2.

Constraints

-2^31 <= val <= 2^31 - 1pop, top, getMin are only called on a non-empty stackAt most 3 * 10^4 calls total across all methods

Pattern lesson

See the pattern, then code

Stack augmented with running minimum

↗

Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. Pair each value with the minimum of everything at or below it. Since a pop only removes the top, the min of the remaining stack is simply the min stored on the new top.

New words, made simpleKnow these before the algorithm

Amortized/O(1) minimum: Returning the smallest element without scanning, by keeping the answer cached.
Prefix minimum: The minimum among all elements from the bottom up to a given position.
Auxiliary state: Extra data stored per element to answer queries faster.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Scan on getMin

Violates the O(1) requirement for getMin.

Keep a plain stack and iterate through all elements whenever getMin is called.

Time O(n) per getMinSpace O(n)

Best choicePair each value with its min

Every operation is constant time and pop naturally restores the previous minimum.

Store (value, min-so-far) so the top always carries the current minimum.

Time O(1) per opSpace O(n)

The rule we keep true

Invariant

For every entry on the stack, its second component equals the minimum of all values from the bottom of the stack up to and including that entry.

Why this is correct

Reasoning

Because a stack only removes from the top, after any pop the remaining elements are exactly a prefix of what came before, and the min of that prefix is already cached on the new top. Push extends the prefix by one, whose min is the smaller of the new value and the old top's cached min, so the invariant is maintained with O(1) work.

The algorithm in three movesSay these aloud before coding

1Store pairs (value, min-so-far) on one stack

push -2 -> [(-2,-2)]

2On push, compute min of the new value and the previous top's stored min

push 0 -> [(-2,-2),(0,-2)]

3On pop, remove the top pair

push -3 -> [...,(-3,-3)]

4top returns the value of the top pair

getMin -> -3

5getMin returns the stored min of the top pair

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-20

-32

1 · Read-2

2 · AskNew min-so-far?

3 · Update state[(-2,-2)]

4 · Resultmin is -2, store pair

Key takeaway

Each cell stores its value and the minimum of everything beneath it, so getMin reads the top's min.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-7Push with cached min
The new minimum is the smaller of the pushed value and the previous top's cached minimum.
2
Lines 9-10Pop
Removing the top pair automatically exposes the correct min for the shorter stack.
3
Lines 12-13top
Returns the value half of the top pair.
4
Lines 15-16getMin
Returns the cached min half of the top pair in O(1) with no scanning.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Duplicate minimum values pushed multiple times
A single element where value and min coincide
Popping down so the minimum reverts to a larger earlier value
Extreme 32-bit values near -2^31 and 2^31-1

Common beginner mistakes

Using a single scalar min variable that becomes stale after popping the current minimum
With a separate min-stack, forgetting to also pop the min-stack (or using strict < so equal mins desync)
Recomputing the minimum by scanning, breaking the O(1) contract

Check your understanding

Why does storing the min alongside each value handle pops correctly, whereas a single min variable does not?

Min Stack

Min Stack

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Stack and Expression Processing