Monotonic Stack
What is this?
A queue of people of different heights, each looking forward. You can see the person immediately ahead, and anyone beyond them as long as everyone in between is shorter than both of you. A taller person in the gap blocks the view past them. Count what each person sees.
Walk the queue from the back with a stack whose heights increase from the top down, and every pop is a person this one can see. The answer is not something you compute after the sweep; it accumulates during it.
Fun fact: Create Maximum Number is two techniques stacked. First, picking the largest possible
k-digit subsequence from one array is a monotonic stack with a budget: pop a smaller digit only while enough digits remain to still fill the quota. Then the two selections are merged by repeatedly taking from whichever array is lexicographically greater from its current position onward (comparing suffixes, not single digits, because equal leading digits must be broken by what follows). Trying every split ofkbetween the two arrays wraps both.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: keep the candidates that could still matter, in an order that makes the irrelevant ones obvious, and treat every pop as the moment an answer is produced rather than as bookkeeping.
1. The pop as a count
res = [0] * n
stack = [] # heights, decreasing from bottom to top
for i in range(n - 1, -1, -1):
count = 0
while stack and stack[-1] < heights[i]:
stack.pop(); count += 1 # each shorter person ahead is visible
if stack:
count += 1 # plus the first taller person
res[i] = count
stack.append(heights[i])
The if stack: count += 1 is the whole subtlety. Everyone popped is visible, and the first person not popped, the taller one, is also visible, because they block the view rather than being hidden by it. Forgetting that undercounts by exactly one for everyone who has a taller person somewhere to their right. The lesson's heights are distinct, so ties do not come up. A strictly decreasing queue and a strictly increasing one both give [1, ..., 1, 0].
2. The pop as a collision
Car Fleet II processes cars from the last to the first with a stack of cars ahead that are still possible targets. Two rules pop a car j ahead of car i:
jis not slower thani, soicannot catch it on its own; orjhas a collision timeans[j], andiwould reachjat a time at or afterans[j], sojhas already merged into something slower andiis really chasing that.
What remains on top after the popping is the car or fleet this one actually hits, and the collision time is (posAhead - pos) / (speed - speedAhead). The second rule compares against a quantity, the collision time, that is not in the input and is derived as the sweep proceeds. A car with ans[j] == -1 never merges, so the second rule never pops it. The lesson covers a bug where that guard is skipped and the stack empties on every car.
3. The wrap
Next Greater Element II is the ordinary forward next-greater sweep over a circular array, run as two laps. Iterate 2n times indexing with % n, and only push during the first lap. The second lap exists solely to resolve elements left unmatched, not to add new candidates.
4. A 30-second worked example (visible people)
heights = [10, 6, 8, 5, 11, 9]
Check person 0 by hand: they see 6, then 8 (taller than 6), then 11, which is three people. The 5 is hidden behind the 8 and the 9 behind the 11, so the answer for person 0 is 3.
5. Where you'll actually meet this
Mostly in interviews. The shapes that transfer:
- Who can see whom along a line. Skyline and rooftop visibility questions, and next-greater variants. Treat it as a pattern drill rather than a famous production algorithm.
- Circular scans. Any "next larger value" question over data that wraps around, handled with
2niterations and% n. - Trimming a sequence under a budget. Largest result after deleting digits while keeping order, which is the budgeted stack in Create Maximum Number.
- Collision and merge simulations. Car Fleet II is a puzzle about merging fleets. The useful part is the habit of asking what each pop means.
6. Problems in this chapter
Number of Visible People in a Queue
How many people each person can see. Sweep from the back with a decreasing stack; every pop is visible, plus the first blocker.
Pattern: pop-as-count. Target: O(n) time, O(n) space.
Next Greater Element II
Next greater element in a circular array. A forward scan of two laps, iterating 2n with % n and pushing only on the first lap.
Pattern: circular monotonic stack. Target: O(n) time, O(n) space.
Car Fleet II
For each car, when it collides with the car or fleet ahead. Sweep from the last car to the first with two pop rules: pop a car that is not slower, and pop a car that has already merged (its collision time is at or before when this car would reach it).
Pattern: pops decided by a derived collision time. Target: O(n) time, O(n) space.
Create Maximum Number
Largest k-digit number from two arrays preserving order. Monotonic-stack selection with a budget from each array, then a suffix-comparing greedy merge, over every split of k.
Pattern: budgeted selection + lexicographic merge. Target: O(k·(m+n) + k³) worst case.
7. Common pitfalls
- Forgetting the blocker. The first person not popped is still visible; missing them undercounts by one.
- Popping with the wrong comparison in the visibility sweep. Pop strictly shorter people; the first taller person stays on the stack and is counted once.
- Pushing during the second lap of the circular sweep, which lets an index resolve against its own value.
- Comparing single digits in the merge. Equal leading digits must be resolved by comparing the remaining suffixes.
- Ignoring the budget in the digit selection: you may only pop while enough digits remain to reach
k. - Quoting
O(k^2(m+n))for Create Maximum Number. The merge can walk up tokdigits per step on ties, so the worst case isO(k·(m+n) + k³). - Dividing by zero in the collision time when two cars share a speed. That case is a pop, not a computation.
- Skipping the
ans[j] != -1guard in Car Fleet II. Every candidate time is positive, so comparing against-1pops everything. - Claiming O(n²) for the monotonic sweeps. Each index enters and leaves once; say so before being asked.
8. Key takeaways
- The pop is the answer, not a step toward it. Decide its meaning first.
- The blocker counts too. The element that stops the sweep is part of the result.
- Pops can depend on a derived value, like a collision time computed during the walk.
- Circular means two laps (
2niterations with% n), not a doubled array, and no pushes on the second lap. - Budgeted popping is how selection problems keep enough digits to finish.
- Compare suffixes, not characters, when merging for lexicographic maximum.
- Where the difficulty is: the sweep is familiar, so the work is in modelling what a pop means. Car Fleet II is the clearest case, because its two pop rules do not follow from the easier problems.
Order: Number of Visible People in a Queue → Next Greater Element II → Car Fleet II → Create Maximum Number.
Calculating Vehicle Collision Times in Fleet Formation
Core idea: Walk the cars from the front of the road to the back, keeping a stack of cars ahead that are still possible targets. A car
icatches a slower carjat time(pos_j - pos_i) / (speed_i - speed_j), but only ifjhas not already merged into something slower before then. So pop every stacked car that is not slower thani, and every stacked car whose own collision time is at or before the timeiwould reach it. What is left on top is the real target. Each car is pushed and popped once, so the whole pass is O(n).
Problem, rephrased
A one-lane highway carries n cars, all heading the same way with no passing. cars[i] = [position_i, speed_i], and positions are strictly increasing, so car i+1 starts ahead of car i. When a car reaches the car ahead, the two lock together into a fleet that moves at the slower car's speed.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson