</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

The monotonic stack loop where each pop is an answer

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.


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:

  • j is not slower than i, so i cannot catch it on its own; or
  • j has a collision time ans[j], and i would reach j at a time at or after ans[j], so j has already merged into something slower and i is 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]

Worked trace of visible people in a queue

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 2n iterations 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 to k digits per step on ties, so the worst case is O(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] != -1 guard in Car Fleet II. Every candidate time is positive, so comparing against -1 pops everything.
  • 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. Pops can depend on a derived value, like a collision time computed during the walk.
  4. Circular means two laps (2n iterations with % n), not a doubled array, and no pushes on the second lap.
  5. Budgeted popping is how selection problems keep enough digits to finish.
  6. Compare suffixes, not characters, when merging for lexicographic maximum.
  7. 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.

Create Maximum Number

Core idea: Two problems stacked. First, the best subsequence of a fixed length from one array: sweep with a monotonic stack and pop a smaller digit whenever enough digits remain to still reach the length (Remove K Digits, run for the largest result). Second, merging two chosen subsequences into the largest sequence: at each step take from the array whose remaining suffix is lexicographically larger, because a tie on the leading digit is broken by what follows. Then try every split of k between the two arrays and keep the best candidate.

Problem, rephrased

A prize-draw machine holds two paper ribbons of digits, one from each of two ticket printers. You're given two digit arrays nums1 (length m) and nums2 (length n), read top to bottom, and an integer k <= m + n, the length of the serial number you must assemble.

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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.