Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Stack

The monotonic stack

Lesson · 11 min read · Stack · The monotonic stack

Which way the stack slopes, how to look backwards as well as forwards, and how to treat equal values so that each subarray is counted exactly once.

Deciding which way the stack slopes

Every problem in this module asks, for each element, about the nearest element on one side that's larger (or smaller) than it. Before writing any code I'd probably decide two things, because I think they determine the whole loop. The first is what you're looking for (larger or smaller) and the second is which side it's on.

If you want the next larger element you keep the elements that are still waiting, and as you saw in the introduction their values decrease from the bottom of the stack to the top. If you want the next smaller element it's the other way round and the stack increases. However, the comparison in the while loop is basically the question you're asking. You keep popping for as long as the new element happens to be the answer for whatever is sitting on top, and I suspect that once you've written it this way a couple of times you won't need to think about it any more.

Looking backwards at the previous higher day

The stock span problem asks, for each day, how many consecutive days up to and including today had a price no higher than today's. That's really asking for the previous day with a strictly higher price, so you're looking backwards at days you've already processed.

The loop is almost the same, however the answer is read at a different moment. You pop every day whose price is no higher than today's (they're hidden behind today for good, since any later day that gets past today gets past them as well) and then whatever is left on top is the previous higher day. If the stack is empty there isn't one and the span goes all the way back to the first day.

Stock span

spans(price)

  1. Start with an empty stack of day indices.
  2. For day i: while the stack is not empty and price[top] ≤ price[i], pop.
  3. span[i] = i − top if the stack still has a top, otherwise i + 1. Then push i.
TimeO(n)
SpaceO(n)

Each day is pushed once and popped at most once, which as far as I can tell is exactly the same accounting as for the next larger element.

Prices 100, 80, 60, 70, 60, 75, 85, where the spans come out as 1, 1, 1, 2, 1, 4, 6.

  1. Step 1 / 8
    prices
    1000801602703604755856
    span
    ·0·1·2·3·4·5·6
    stack[]

    I'd keep a stack of the days that are still visible, and you'll see that their prices always go down from the bottom to the top.

  2. Step 2 / 8
    prices
    1000801602703604755856
    span
    10·1·2·3·4·5·6
    stack[0]

    Nothing gets popped for 100 on day 0, and there's nothing earlier that's higher so the span goes right back to the start and it's 1.

  3. Step 3 / 8
    prices
    1000801602703604755856
    span
    1011·2·3·4·5·6
    stack[0, 1]

    Day 1 at 80 doesn't hide anything, and the nearest higher day is day 0 at 100 so the span is 1 − 0 = 1.

  4. Step 4 / 8
    prices
    1000801602703604755856
    span
    101112·3·4·5·6
    stack[0, 1, 2]

    Nothing gets popped for 60 on day 2, and the nearest higher day is day 1 at 80 so the span is 2 − 1 = 1.

  5. Step 5 / 8
    prices
    1000801602703604755856
    span
    10111223·4·5·6
    stack[0, 1, 3]

    Day 3 at 70 hides day 2 so it comes off the stack, and the nearest higher day is day 1 at 80 so the span is 3 − 1 = 2.

  6. Step 6 / 8
    prices
    1000801602703604755856
    span
    1011122314·5·6
    stack[0, 1, 3, 4]

    Nothing gets popped for 60 on day 4, and the nearest higher day is day 3 at 70 so the span is 4 − 3 = 1.

  7. Step 7 / 8
    prices
    1000801602703604755856
    span
    101112231445·6
    stack[0, 1, 5]

    Day 5 at 75 hides days 3 and 4 so they come off the stack, and the nearest higher day is day 1 at 80 so the span is 5 − 1 = 4.

  8. Step 8 / 8
    prices
    1000801602703604755856
    span
    10111223144566
    stack[0, 6]

    Day 6 at 85 hides days 1 and 5 so they come off the stack, and the nearest higher day is day 0 at 100 so the span is 6 − 0 = 6.

Equal values and counting each subarray once

Some problems want a total over every subarray, for example the sum of the minimum of every subarray. Trying all of them is O(n²) at best. Generally I'd recommend asking, for each element, in how many subarrays it's the minimum. If the previous smaller element is L places to the left and the next smaller one is R places to the right, then the element is the minimum of L × R subarrays and it contributes a[i] × L × R to the total. Two passes of a monotonic stack (one from the left and one from the right) should give you every L and R in linear time.

Unfortunately the difficulty is equal values. With [2, 2] the subarray containing both has two minimums and you'd count it twice if both sides used the same comparison. So you make the two sides different on purpose, with strictly smaller on the left and smaller or equal on the right, and then every subarray belongs to exactly one element (the leftmost of its minimums). It's easy to get this wrong under pressure, so I'd suggest testing it on an array where every value is the same.

On [3, 1, 2, 4] the ten subarrays have minimums adding up to 17. The 1 is the minimum of 2 × 3 = 6 of them, which is 6 of the 17 on its own.

The largest rectangle

The largest rectangle in a bar chart uses the same two neighbours. If a rectangle is limited by bar i, then it's as tall as that bar and it stretches from just after the previous shorter bar to just before the next shorter one. Therefore you compute both neighbours for every individual bar and take the largest height × width. You can also do it in a single pass, since the moment a bar is popped you know its next shorter bar (the one doing the popping) and its previous shorter bar (the one underneath it on the stack).

Problems in this module