Coding Interview Patterns Module 8 – Stacks and monotonic stacks
Stacks that know their minimum
Design a stack whose push, pop, top and minimum each take O(1): an original fuel-log problem, the scan that fails at 10⁵ calls, and the key idea.
What you will learn
- Support push, pop, top and the minimum in O(1) time, and prove the design correct
- Store pairs or a second stack of minimums, and compare their memory with measured numbers
- Avoid the duplicate-minimum and boxed-integer slips, and the overflow of the encoded single stack
- Build a queue with an amortised O(1) minimum from two stacks
Before you start
What you’ll learn · Before you start
What you will learn
- Support push, pop, top and the minimum in O(1) time, and prove the design correct
- Store pairs or a second stack of minimums, and compare their memory with measured numbers
- Avoid the duplicate-minimum and boxed-integer slips, and the overflow of the encoded single stack
- Build a queue with an amortised O(1) minimum from two stacks
Before you start
On this page
A min stack: A stack that can also report its smallest value at any moment, with push, pop, top and the minimum each in O(1) time, because each level remembers the minimum at or below it. is a stack that can also report its smallest value at any moment, with push, pop, top and the minimum each in O(1) time. It is needed wherever the newest item can be taken back while a running best must stay right: undo in a ledger, backtracking with a best-so-far, the cheapest fill-up on a road trip. Scanning the whole stack for the minimum costs O(n) per question, which is far too slow at 10⁵ operations. The fix rests on one observation: a stack only ever removes its newest item, so the minimum of everything below an item cannot change while that item is there, and each level can remember it. Below are an original version of the problem, a measured brute force and the signal that leads to the fix.
The problem: the cheapest fill-up of a trip
The problem
A fuel-log app records the price per litre of each fill-up on a road trip, as a whole number of the smallest
currency unit. The driver may undo the latest fill-up, and the app must always show the cheapest price among the
fill-ups still in the log. Write a class with fill(price), undo(), latest() and cheapest(), each in O(1)
time. There are at most 2 × 10⁵ operations, every price is from 1 to 10⁹, and undo, latest and cheapest are
called only when the log is not empty.
Two examples, run by every version of the code below:
- Fill 9472, 9310 and 9655: the cheapest is 9310. After two undos only 9472 is left, so the cheapest and the latest are both 9472.
- Fill 9310 twice and undo once: the cheapest is still 9310, because one fill-up at that price remains.
The brute force: scan the log
Keep the prices on a plain stack and let cheapest() look at every one of them. Filling, undoing and reading the
latest price stay O(1), but each cheapest() costs O(n), so 10⁵ fill-ups followed by 10⁵ calls scan 10¹⁰ prices.
"""The brute force: a plain stack of fill-ups that scans every price for cheapest()."""
import random
import time
class ScanLog:
def __init__(self):
self.prices = []
def fill(self, price):
self.prices.append(price)
def undo(self):
self.prices.pop()
def latest(self):
return self.prices[-1]
def cheapest(self):
return min(self.prices) # looks at every fill-up still in the log: O(n)
log = ScanLog()
for price in (9472, 9310, 9655):
log.fill(price)
print("example 1:", log.cheapest(), end=" ")
log.undo()
log.undo()
print(log.cheapest(), log.latest())
log = ScanLog()
log.fill(9310)
log.fill(9310)
log.undo()
print("example 2:", log.cheapest())
rng = random.Random(11)
per_price = 0.0
for n in (1_000, 2_000, 4_000):
log = ScanLog()
for _ in range(n):
log.fill(rng.randrange(8_000, 11_000))
best = float("inf")
for _ in range(3): # the fastest of three runs: the least disturbed by other programs
start = time.perf_counter()
for _ in range(n):
log.cheapest()
best = min(best, time.perf_counter() - start)
per_price = best / (n * n)
print(f"n = {n:,}: {n:,} fill-ups, then {n:,} cheapest() calls scan {n * n:,} prices in {best * 1000:,.0f} ms")
# Every call scans all n prices, so the work grows with n squared.
print(f"n = 100,000: {100_000 * 100_000:,} prices, about {100_000 * 100_000 * per_price / 60:,.0f} minutes at that speed")Output
example 1: 9310 9472 9472 example 2: 9310 n = 1,000: 1,000 fill-ups, then 1,000 cheapest() calls scan 1,000,000 prices in 12 ms n = 2,000: 2,000 fill-ups, then 2,000 cheapest() calls scan 4,000,000 prices in 165 ms n = 4,000: 4,000 fill-ups, then 4,000 cheapest() calls scan 16,000,000 prices in 604 ms n = 100,000: 10,000,000,000 prices, about 6 minutes at that speed
This output changes from run to run: the times depend on the computer and on what else it is doing
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 scan_log.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Each doubling of n scans four times as many prices. At the limit, the recorded run puts 10¹⁰ prices at minutes of work, where a time limit allows about a second.
Checkpoint
Check: What scanning the log costs
What to notice
The cheapest price changes only when a fill-up brings a lower price, or when an undo removes the fill-up that set it, and then it returns to exactly what it was before that fill-up. So the cheapest price belongs to each level of the log: the minimum of that level and everything below it, which stays the same while the level is there.
Each level knows the cheapest price at or below it
Text description of the diagram
The diagram shows the fuel log after three fill-ups, with the newest one at the top, drawn with a thick border.
- The top level holds the price 9655. The cheapest price at or below it is 9310.
- The middle level holds 9310. The cheapest price at or below it is 9310, its own.
- The bottom level holds 9472, the first fill-up. The cheapest price at or below it is 9472.
An arrow labelled "undo, undo" leads to the state after two undos: only 9472 is left, and its level already says that the cheapest price is 9472. The cheapest price at or below a level never changes while that level is in the log, because a stack only ever removes its newest level.
Three designs build on this observation:
- Pairs: each level stores its price together with the cheapest price at or below it.
- A second stack of minimums: it takes a price only when the price is at most the current cheapest.
- One encoded stack: it stores a new minimum as twice the price minus the old minimum, with no second stack.
Checkpoint
Check: The minimum each level can remember
These questions cover the scan and the signal, weakest idea first.
Practice that adapts to you
Practise this lesson
6 questions about 9 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Pairs: every level remembers its cheapest Pro: opens with a Pro, Premium or Ultimate pass
In this part:
- A second stack keeps only the minimums, repeats included
- The < slip, reproduced: a repeated minimum lost
- Memory, measured: pairs against a second stack
- The code in 14 languages
- The Java slip, reproduced: comparing boxed integers with ==
- One stack and one variable: the encoded trick, and where 32 bits break it
- A queue that knows its minimum, from two stacks
- Edge cases, common bugs and variants
- Variants, with answers
- Practise: a min stack with sample tests
- Build a stack that knows its minimum
- Interview questions
- A Java min stack keeps a second ArrayDeque<Integer> of minimums. It passes every test with small numbers, but in production, with prices in the thousands, cheapest() sometimes returns a price that was undone. Find the likely bug, explain why the small tests miss it, and fix it.
- A min stack must hold up to 10⁸ 32-bit readings on a device with 1 GB of memory. Compare pairs, a second stack of minimums and the encoded single stack: what does each cost in the worst case, and which do you ship?
- Prices arrive one per second, and after each one a dashboard shows the lowest price of the last 600 seconds. Design it with O(1) amortised work per price, prove the bound, and say what the slowest single update costs.
- Key takeaways
2 diagrams · 6 runnable examples (Java, Python) · 1 exercise with sample tests · 3 interview answers · about 38 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Terms in this lesson
- min stack
- A stack that can also report its smallest value at any moment, with push, pop, top and the minimum each in O(1) time, because each level remembers the minimum at or below it.
References
- The Python Tutorial: Using Lists as Stacks (Python Software Foundation)
- tracemalloc: trace memory allocations (Python Software Foundation)
- Private elements (#fields) in classes (MDN Web Docs (Mozilla))
- Java SE 25 API: ArrayDeque (Oracle)
- Java SE 25 API: Integer.valueOf(int) (Oracle)
- The Java Tutorials: Autoboxing and Unboxing (the compiler calls Integer.valueOf) (Oracle)
- The Java Language Specification, Java SE 25: 5.1.7 Boxing Conversion (Oracle)
- The Java Language Specification, Java SE 25: 4.2.2 Integer Operations (Oracle)
- std::vector (cppreference.com)
- The Go Programming Language Specification: Appending to and copying slices (The Go Authors)
- Equality (Kotlin documentation): structural equality with == (JetBrains)
- Equality operators (C# reference): value types are equal if their contents are equal (Microsoft)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress