Foundations · pattern 7 of 10

Monotonic stack

A monotonic stack is a stack kept in order: from bottom to top its values only go down, or only go up. A new value takes off every value that breaks the order. The one left under it is its nearest larger or smaller neighbor.

Watch it run in the app

When to use it

Use it when every item needs the nearest item before or after it that is larger, or smaller, than itself.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

Buildings stand in a row along a street. Each number is the height of one building, in floors. For each building, return the height of the nearest taller building to its left, or 0 if no building to its left is taller.

Input
heights = [5, 3, 4, 2, 6, 1, 3]

Output
[0, 5, 5, 4, 0, 6, 6]

The method

Start with an empty stack and an empty answer
Take off every building that is not taller than this one
Note the top that is left, or 0, then put this one on top
Every building has its answer: return the list

The run, one moment at a time

Step 1. No building has been looked at. The stack and the answer are empty.
```
heights: 5 3 4 2 6 1 3
stack: empty
taller: empty
```
Step 3. The stack is empty, so no building to the left of 5 is taller. Its answer is 0. Then 5 goes on the stack.
```
heights: 5 3 4 2 6 1 3
stack: 5  (top at 0)
taller: 0
```
Step 3. 5 on top is taller than 3, so nothing comes off and the answer for 3 is 5. Then 3 goes on top.
```
heights: 5 3 4 2 6 1 3
stack: 5 3  (top at 1)
taller: 0 5
```
Step 2. 4 is at least as tall as 3, and it stands nearer to every building that comes later. So 3 can never be the answer again: take it off.
```
heights: 5 3 4 2 6 1 3
stack: 5 3  (top at 0)
taller: 0 5
```
Step 3. 5 is left on top and it is taller than 4, so the answer for 4 is 5. Then 4 goes on top.
```
heights: 5 3 4 2 6 1 3
stack: 5 4  (top at 1)
taller: 0 5 5
```
Step 3. 4 on top is taller than 2, so nothing comes off and the answer for 2 is 4. Then 2 goes on top.
```
heights: 5 3 4 2 6 1 3
stack: 5 4 2  (top at 2)
taller: 0 5 5 4
```
Step 2. 6 is at least as tall as 2, 4 and 5, and it stands nearer to every building that comes later. So 2, 4 and 5 can never be the answer again: take them off.
```
heights: 5 3 4 2 6 1 3
stack: 5 4 2
taller: 0 5 5 4
```
Step 3. The stack is empty, so no building to the left of 6 is taller. Its answer is 0. Then 6 goes on the stack.
```
heights: 5 3 4 2 6 1 3
stack: 6  (top at 0)
taller: 0 5 5 4 0
```
Step 3. 6 on top is taller than 1, so nothing comes off and the answer for 1 is 6. Then 1 goes on top.
```
heights: 5 3 4 2 6 1 3
stack: 6 1  (top at 1)
taller: 0 5 5 4 0 6
```
Step 2. 1 on the stack is not taller than 3, so it cannot be the answer for 3. Take it off, as before.
```
heights: 5 3 4 2 6 1 3
stack: 6 1  (top at 0)
taller: 0 5 5 4 0 6
```
Step 3. 6 is left on top and it is taller than 3, so the answer for 3 is 6. Then 3 goes on top.
```
heights: 5 3 4 2 6 1 3
stack: 6 3  (top at 1)
taller: 0 5 5 4 0 6 6
```
Step 4. All 7 buildings have an answer. Each went on the stack once and came off at most once: 7 pushes and 5 pops in all.
```
heights: 5 3 4 2 6 1 3
stack: 6 3  (top at 1)
taller: 0 5 5 4 0 6 6
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(heights) {
  // 1. Start with an empty stack and an empty answer
  const stack = [];
  const taller = [];
  for (const height of heights) {
    // 2. Take off every building that is not taller than this one
    while (stack.length > 0 && stack[stack.length - 1] <= height) {
      stack.pop();
    }
    // 3. Note the top that is left, or 0, then put this one on top
    if (stack.length > 0) {
      taller.push(stack[stack.length - 1]);
    } else {
      taller.push(0);
    }
    stack.push(height);
  }
  // 4. Every building has its answer: return the list
  return taller;
}

Python

def solve(heights):
    # 1. Start with an empty stack and an empty answer
    stack = []
    taller = []
    for height in heights:
        # 2. Take off every building that is not taller than this one
        while stack and stack[-1] <= height:
            stack.pop()
        # 3. Note the top that is left, or 0, then put this one on top
        if stack:
            taller.append(stack[-1])
        else:
            taller.append(0)
        stack.append(height)
    # 4. Every building has its answer: return the list
    return taller

How to spot it

Asked: For each item, the next later item that is larger: Items wait on the stack. A larger arrival takes off every smaller one, and it is the answer for each of them.
Asked: The nearest earlier item that is smaller than this one: Take off the earlier items that are not smaller. The top that is left is the nearest smaller one.
Asked: How far an item reaches before a lower one stops it: The reach ends at the nearest lower item on each side. One ordered stack finds both ends for every item.
Limits: Up to 100,000 items, so looking back for a larger one is too slow: Looking back from every item can take about 5 billion steps. On the stack each item goes on once and comes off at most once.

Looks like it, but is not

You need the largest value in every block of k items in a row. Use Monotonic queue. Old items also leave at the far end when the block moves on. A stack cannot remove from that end.
For each position you need the largest value anywhere before it, not the nearest larger one. Use Prefix and suffix passes. One running maximum carried from left to right answers that. Nearness does not matter, so no stack is needed.
Items open and close in nested pairs, and their sizes are never compared. Use Last-in, first-out stack. A plain stack is enough. Nothing has to be taken off because a larger or smaller value arrived.

Cost and mistakes

Time is about 2n steps for n items, written O(n). Each item goes on the stack once and comes off at most once, whatever the inner loop looks like. Extra space is the stack, at most n entries.

Watch out

Decide what an equal value does. Here <= takes an equal building off, because equal is not taller. With < it would stay on the stack and be given as the answer.
When the answer is a distance or a position, keep positions on the stack, not values. A position still gives you the value. A value cannot give you the position.

In the 150

3 problems of the 150 use it. Naming them gives their method away, so the list is folded.

Show the 3

Daily TemperaturesMedium · Stack
Car FleetMedium · Stack
Largest Rectangle In HistogramHard · Stack