Monotonic Stack

What is this?

A queue of people of different heights, each looking forward. You can see the person immediately ahead, and anyone taller than everyone between you and them — your view is blocked the moment someone at least as tall stands in the way. Count what each person sees.

Walk the queue from the back with a stack of decreasing heights, 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 of k between the two arrays wraps both.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line 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, strictly decreasing
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 person at least as tall
    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 one at least as tall — is also visible, because they are what blocks the view rather than being hidden by it. Forgetting that undercounts by exactly one everywhere the view is blocked.

2. The pop as a collision

Car Fleet II processes cars from the back with a stack of cars ahead that are still relevant. A car ahead becomes irrelevant when either:

• it is faster or equal, so it can never be caught; or
• it collides with something else first, at a time earlier than when this car would reach it.

Both are pops. What remains on top after the popping is the car this one actually hits, and the collision time is (posAhead − pos) / (speed − speedAhead). The stack is therefore monotonic in a quantity — collision time — that does not exist in the input and is derived as the sweep proceeds.

3. The wrap

Next Greater Element II is the ordinary next-greater sweep over a circular array. Iterate 2n times indexing with % n, and only push during the first pass — the second pass 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]

i=5  h=9   stack empty          → count 0                  push 9    [9]
i=4  h=11  pop 9 (count 1)      stack empty → no blocker    → 1      push 11   [11]
i=3  h=5   11 > 5, no pops      stack non-empty → +1        → 1      push 5    [11,5]
i=2  h=8   pop 5 (count 1)      11 > 8 → +1                 → 2      push 8    [11,8]
i=1  h=6   8 > 6, no pops       stack non-empty → +1        → 1      push 6    [11,8,6]
i=0  h=10  pop 6, pop 8 (2)     11 > 10 → +1                → 3      push 10   [11,10]

result: [3, 1, 2, 1, 1, 0]

Check person 0 by hand: they see 6, then 8 (taller than 6), then 11 — three people. The 5 and the 9 are hidden behind taller people. ✓

5. Where you'll actually meet this

• Traffic simulation. Convoy formation and collision prediction, which is Car Fleet II with real vehicles and real timestamps.
• Rendering and occlusion. Determining which objects along a sight line are visible.
• Financial data. Span indicators — how many consecutive prior periods a value dominates — computed incrementally over a stream.
• Number formatting. Selecting the largest or smallest representation under a digit budget.
• Skyline and terrain analysis. Visibility from a point across a height profile.

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. Iterate 2n with % n, pushing only on the first pass.
Pattern: circular monotonic stack. Target: O(n) time, O(n) space.

▶ Car Fleet II

For each car, when it collides with the car ahead. Sweep from the back, popping cars that are faster or that collide earlier than this car could reach them.
Pattern: monotonic in 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((m+n)³) worst case.

7. Common pitfalls 🚫

• Forgetting the blocker. The first person not popped is still visible; missing them undercounts by one.
• Using <= instead of < in the visibility pop. Equal heights block the view, so they must not be popped.
• Pushing during the second pass of the circular sweep, which invents elements that do not exist.
• 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.
• Dividing by zero in the collision time when two cars share a speed — that case is a pop, not a computation.
• Claiming O(n²) for the monotonic sweeps. Each index enters and leaves once; say so before being asked.

8. Key takeaways

1. The pop is the answer, not a step toward it. Decide its meaning first.
2. The blocker counts too — the element that stops the sweep is part of the result.
3. A stack can be monotonic in a derived value, like a collision time computed during the walk.
4. Circular means 2n iterations, not a doubled array, and no pushes on the second pass.
5. Budgeted popping is how selection problems keep enough digits to finish.
6. Compare suffixes, not characters, when merging for lexicographic maximum.
7. Why interviewers like it: the sweep is familiar, so all the difficulty is in modelling — and Car Fleet II in particular cannot be pattern-matched from easier problems.

Order: Number of Visible People in a Queue → Next Greater Element II → Car Fleet II → Create Maximum Number.