cf.completefrontend
STACKS & QUEUES · CORE

Min stack

A stack that can also tell you its smallest item in O(1), by remembering the minimum at every height.

Time O(1) per operationSpace O(n)3 practice problemsStep-through picture

The idea

A normal stack can push, pop, and show its top in O(1). Finding its smallest item means scanning everything, which is O(n). A min stack makes that O(1) too.

The idea: next to each item, store the smallest value in the stack at the moment that item was pushed. Since a stack only changes at the top, the minimum for the items below never changes. When you pop, the minimum stored with the new top is again correct.

This works in a second array, mins, that grows and shrinks together with items. The same trick gives a max stack, or any running summary that only depends on the items below.

An everyday example

A stack of boxes with a sticky note on each

A warehouse worker stacks boxes of different weights. On each box they stick a note: "lightest box from here down". To find the lightest box in the whole stack, they just read the note on the top box. When they take the top box away, the note on the box below is still true, because nothing under it changed.

How the example maps to the code
In the exampleIn the code
The stack of boxesthis.items
The sticky notesthis.mins
Writing the note when a box is addedMath.min(value, this.mins[this.mins.length - 1])
Reading the top notegetMin()

From the slow way to min stack

  1. Start with the obvious getMin: scan every item on the stack and return the smallest. Push and pop stay O(1), but every getMin costs O(n). If code calls it after each push, n pushes cost O(n^2).
  2. The next idea is one variable, min, updated on every push with Math.min. Push is fine. Pop breaks it: if the popped item was the minimum, what is the new minimum? The variable doesn't know, and finding out needs the scan again.
  3. Look at what a stack allows. Items only change at the top. So the items below the top stay exactly the same while they sit there, and so does their minimum. If you write down the minimum of the bottom h items when the hth item is pushed, that note stays true until that item is popped.
  4. So keep a second array, mins, as tall as the stack: mins[h] is the smallest of items[0] to items[h]. Push computes the new entry from the one below, pop removes both tops, and the answer is always the top of mins. That pair of arrays is the min stack.

How it works

  1. Keep two arrays of the same length: items for the values and mins for the minimum at each height.
  2. To push value, push it onto items.
  3. Compute the new minimum: value itself if the stack was empty, otherwise the smaller of value and the previous top of mins. Push that onto mins.
  4. To pop, pop both arrays and return the popped item.
  5. top() reads the last item of items, and getMin() reads the last item of mins.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class MinStack {
  2. constructor() {
  3. this.items = [];
  4. this.mins = [];
  5. }
  7. push(value) {
  8. this.items.push(value);
  9. const min = this.mins.length === 0 ? value : Math.min(value, this.mins[this.mins.length - 1]);
  10. this.mins.push(min);
  11. }
  13. pop() {
  14. this.mins.pop();
  15. return this.items.pop();
  16. }
  18. top() {
  19. return this.items[this.items.length - 1];
  20. }
  22. getMin() {
  23. return this.mins[this.mins.length - 1];
  24. }
  25. }

How fast it is

TimeO(1) per operation
Extra memoryO(n)

Each method touches only the ends of two arrays. Storing one minimum per item uses about twice the memory of a plain stack.

  • Best caseO(1)

    Any push, top, or getMin: each reads or writes only the ends of the arrays.

  • Average caseO(1)

    Any mix of calls. No method has a loop.

  • Worst caseO(1)

    A pop that removes the current minimum. This is the case that would force a scan with a single min variable, and here it only removes two array ends.

Common mistakes

  • Keeping a single min variable. After popping the minimum, you don't know the next smallest without a scan.
  • Forgetting to pop mins in pop(), so the two arrays drift apart and getMin() reports a value that is gone.
  • In the memory-saving version, pushing onto mins only when the value is strictly smaller, which breaks when the minimum appears twice.

When to use it

Look for these clues in a problem:

  • A class must support push, pop, top, and also get the minimum (or maximum) in O(1).
  • Undo-like history must also report a running extreme, such as the lowest price so far.
  • A stack's items change only at the top, and you need a summary of all of them.

Check yourself

Answer each one in your head first, then open it.

Why can't a single min variable support pop?

When the popped item was the minimum, the variable has no record of the next smallest item. Finding it means scanning the stack, which is O(n).

Why does mins[h] stay correct while items are pushed above it?

It describes only items[0] to items[h], and a stack never changes items below the top. Pushes above it don't touch them.

In the memory-saving version, what breaks with < instead of <=?

Pushing the same minimum twice adds only one entry to mins. Popping one copy then removes that entry, and getMin reports a larger value while the other copy is still on the stack.

After push(5), push(2), push(8), pop(), pop(), what does getMin() return?

5. The two pops remove 8 and 2 along with their mins entries 2 and 2, leaving mins = [5].

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The class keeps one rule after every call: items and mins have the same length, and for every height h, mins[h] is the smallest of items[0] to items[h]. Both arrays start empty, so the rule holds.

push(value) adds value at a new height h. The smallest of the items up to h is either value or the smallest of the items below it, which is mins[h - 1] by the rule. So Math.min(value, mins[h - 1]) is right, and the empty case uses value alone. pop() removes the top of both arrays, and every remaining entry describes items that didn't change, so it is still right.

With the rule, getMin() is the top of mins, which is the smallest of all the items. Nothing ever needs to look below the top, which is why every method is O(1).

Going deeper

3 more ideas

Why the stored minimum stays correct

mins[h] is the smallest of items[0] to items[h]. Pushing adds one item on top and computes mins for the new height from the one below, so the rule holds. Popping removes the top of both arrays; everything below is unchanged, so their mins entries are still right.

Cost

Every method does a fixed number of array operations at the end, so each is O(1). The extra mins array doubles the memory, which is still O(n).

Saving memory with duplicates

A variation pushes onto mins only when the new value is less than or equal to the current minimum, and pops from mins only when the popped item equals it. This uses less memory when the minimum rarely changes. The <= matters: with <, popping one of two equal minimums would wrongly remove the minimum from mins.

Work it by hand

Every step in a table, with why

Run twelve calls, including two pushes of the same minimum, so popping one copy shows the other still counts.

push(6), push(9), push(4), push(4), getMin(), pop(), getMin(), pop(), getMin(), push(7), top(), getMin()

StepCallReturnsitemsminsWhy
1push(6)-[6][6]The stack was empty, so the minimum is the value itself.
2push(9)-[6, 9][6, 6]Math.min(9, 6) is 6: the minimum didn't change.
3push(4)-[6, 9, 4][6, 6, 4]4 is a new minimum, recorded at height 2.
4push(4)-[6, 9, 4, 4][6, 6, 4, 4]A second 4. Its entry in mins is also 4.
5getMin()4[6, 9, 4, 4][6, 6, 4, 4]Read the top of mins. No scan.
6pop()4[6, 9, 4][6, 6, 4]Both tops go. The entry below still says 4, which is right: the other 4 is still there.
7getMin()4[6, 9, 4][6, 6, 4]One copy of the minimum is gone, but the minimum is still 4.
8pop()4[6, 9][6, 6]Now the last 4 leaves, and the new top of mins is 6.
9getMin()6[6, 9][6, 6]The minimum went back up to 6 with no scan, because it was written down when 9 was pushed.
10push(7)-[6, 9, 7][6, 6, 6]Math.min(7, 6) is 6.
11top()7[6, 9, 7][6, 6, 6]top reads items, not mins.
12getMin()6[6, 9, 7][6, 6, 6]The top of mins is 6.

Every call took a fixed number of steps. The two arrays stayed the same length after every call, and getMin() answered 4, 4, 6, 6 without looking at items.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Min stackO(1)O(n)You need push, pop, top, and the minimum, all in constant time.
Plain stack, scan for the minimumO(n)O(n)getMin is called rarely and you'd rather not store extra entries.
Stack plus a heapO(log n)O(n)You need more than the minimum, like the smallest few values, and can accept logarithmic time.

Extra memory: O(n): one mins entry per item, about twice the memory of a plain stack. The memory-saving version stores fewer entries when the minimum rarely changes.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Min stack and the other approaches, on a scale where each line up is 10 times more steps.
  • Min stack O(1)
  • Plain stack, scan for the minimum O(n)
  • Stack plus a heap O(log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Min stack111
Plain stack, scan for the minimum101,0001 million
Stack plus a heap31020

Inputs that need care

5 tricky inputs
pop(), top(), or getMin() on an empty stack
They return undefined, because [].pop() and reading index -1 both give undefined. Throw or return null instead if callers need a clear signal.
The same minimum pushed twice
Each copy gets its own mins entry, so popping one copy leaves the other's entry, as in the trace with two 4s.
Negative numbers and zero
Math.min handles them like any number: pushing -3 after 0 makes the minimum -3.
NaN pushed by mistake
Math.min returns NaN if any argument is NaN, so every mins entry above it becomes NaN too. Pushing 3, NaN, 1 gives mins = [3, NaN, NaN]. Check values before pushing.
Strings like "b"
Math.min turns its arguments into numbers, so "b" becomes NaN. For strings, compare with < and keep the smaller one yourself.

Variations and follow-ups

Twists interviewers add

Store mins only when the minimum changes

Push onto mins only when value <= getMin(), and pop mins only when the popped item equals getMin(). On data where the minimum rarely changes, mins stays short. The <= is needed so that two copies of the minimum get two entries.

Pairs instead of two arrays

Push [value, min] as one entry. It is the same idea with one array, and the two parts can never drift apart.

Max stack, or any running summary

Use Math.max for a max stack. The same trick works for anything you can compute from the item and the summary below it, such as the running sum or the count of even values.

Queue with a minimum

Build a queue from two min-stacks, as in the queue-from-two-stacks method. The queue's minimum is the smaller of the two stacks' minimums, so it is also O(1) on average.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "design a stack that also returns the minimum (or maximum) in O(1)". A class with push, pop, top, and getMin is the giveaway.
  • Explain why one variable fails before showing the fix: "after popping the minimum, I don't know the next one". Then say the key fact: a stack only changes at the top, so the minimum below each item never changes.
  • Test by hand: push the same minimum twice and pop once, then check getMin. Also pop until empty and check that both arrays stay the same length.
  • Expect the follow-up "can you use less memory?". Store a mins entry only when the value is <= the current minimum, and explain why < breaks with duplicates.

Where frontend code uses it

The same idea in real UI code
  • A stack of open modals or layers can store the highest z-index at each level next to each layer, so the next layer knows what to stack above without scanning them all.
  • Undo history in a trading or analytics view can keep the lowest price so far at each step, so undoing restores the right running minimum instantly.
  • Parsers for nested blocks, such as indentation in YAML or Python-like syntax, keep summaries per stack level the same way.

Related algorithms