AlgoScope

Monotonic Stack

A new value pops everything it beats before it lands, so the stack stays sorted. For next-greater, each pop hands the popped value its answer. For previous-greater, each pop throws away a value that can never be an answer again, and whatever is left on top is the answer.

The player

Largest rectangle in a histogram of 6 bars.201152632435

Each value is the height of a bar. The largest rectangle under the histogram is bounded by the nearest shorter bar on each side of some bar. Scan left to right keeping a stack of bars with rising heights: when a lower bar arrives, every taller bar on the stack has found its right bound, and the bar below it on the stack is its left bound. A sentinel of height 0 at the end flushes the stack.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.

  1. Bar 0 of height 2 is popped. Its right bound is index 0 and its left bound index 0. What area does it enclose?

    • 2
    • 4

    Answer: 2. Height times the number of bars between the nearest shorter bars, 2 x 1.

  2. Bar 3 of height 6 is popped. Its right bound is index 3 and its left bound index 3. What area does it enclose?

    • 6
    • 12

    Answer: 6. Height times the number of bars between the nearest shorter bars, 6 x 1.

  3. Bar 2 of height 5 is popped. Its right bound is index 3 and its left bound index 2. What area does it enclose?

    • 10
    • 15

    Answer: 10. Height times the number of bars between the nearest shorter bars, 5 x 2.

  4. Bar 5 of height 3 is popped. Its right bound is index 5 and its left bound index 5. What area does it enclose?

    • 3
    • 6

    Answer: 3. Height times the number of bars between the nearest shorter bars, 3 x 1.

  5. Bar 4 of height 2 is popped. Its right bound is index 5 and its left bound index 2. What area does it enclose?

    • 8
    • 4
    • 10

    Answer: 8. Height times the number of bars between the nearest shorter bars, 2 x 4.

  6. Bar 1 of height 1 is popped. Its right bound is index 5 and its left bound index 0. What area does it enclose?

    • 6
    • 5
    • 7

    Answer: 6. Height times the number of bars between the nearest shorter bars, 1 x 6.

How it runs, step by step

  1. Each value is the height of a bar. The largest rectangle under the histogram is bounded by the nearest shorter bar on each side of some bar. Scan left to right keeping a stack of bars with rising heights: when a lower bar arrives, every taller bar on the stack has found its right bound, and the bar below it on the stack is its left bound. A sentinel of height 0 at the end flushes the stack.

    Largest rectangle in a histogram of 6 bars.

  2. Push bar 0 of height 2: the stack was empty.

    Push bar 0.

  3. Bar 1 has height 1, not taller than the top of the stack, 2 at index 0. Pop it: its rectangle reaches right to index 0 and left to index 0 (no shorter bar on the left), width 1, area 2 x 1 = 2. New best.

    Pop bar 0 of height 2: area 2.

  4. Push bar 1 of height 1: the stack was empty.

    Push bar 1.

  5. Push bar 2 of height 5: it is taller than 1 below it, so the stack still rises.

    Push bar 2.

  6. Push bar 3 of height 6: it is taller than 5 below it, so the stack still rises.

    Push bar 3.

  7. Bar 4 has height 2, not taller than the top of the stack, 6 at index 3. Pop it: its rectangle reaches right to index 3 and left to index 3, just past the shorter bar 2, width 1, area 6 x 1 = 6. New best.

    Pop bar 3 of height 6: area 6.

  8. Bar 4 has height 2, not taller than the top of the stack, 5 at index 2. Pop it: its rectangle reaches right to index 3 and left to index 2, just past the shorter bar 1, width 2, area 5 x 2 = 10. New best.

    Pop bar 2 of height 5: area 10.

  9. Push bar 4 of height 2: it is taller than 1 below it, so the stack still rises.

    Push bar 4.

  10. Push bar 5 of height 3: it is taller than 2 below it, so the stack still rises.

    Push bar 5.

  11. The sentinel of height 0 flushes the stack: top is 3 at index 5. Pop it: its rectangle reaches right to index 5 and left to index 5, just past the shorter bar 4, width 1, area 3 x 1 = 3. Best stays 10.

    Pop bar 5 of height 3: area 3.

  12. The sentinel of height 0 flushes the stack: top is 2 at index 4. Pop it: its rectangle reaches right to index 5 and left to index 2, just past the shorter bar 1, width 4, area 2 x 4 = 8. Best stays 10.

    Pop bar 4 of height 2: area 8.

  13. The sentinel of height 0 flushes the stack: top is 1 at index 1. Pop it: its rectangle reaches right to index 5 and left to index 0 (no shorter bar on the left), width 6, area 1 x 6 = 6. Best stays 10.

    Pop bar 1 of height 1: area 6.

  14. Largest rectangle: area 10 over indices 2 to 3. Every bar is pushed once and popped once, 6 pops in all, so the scan is O(n) although each bar's rectangle can span the whole array.

    Largest rectangle has area 10.

The code

Monotonic Stack, in Python

def next_greater(a):
    answer = [-1] * len(a)
    stack = deque()  # indices, values decreasing bottom to top
    for i in range(len(a)):
        while stack and a[stack[-1]] < a[i]:
            answer[stack.pop()] = a[i]
        stack.append(i)
    return answer  # whatever is still on the stack keeps -1

def previous_greater(a):
    answer = [-1] * len(a)
    stack = deque()
    for i in range(len(a)):
        while stack and a[stack[-1]] <= a[i]:
            stack.pop()
        if stack:
            answer[i] = a[stack[-1]]
        stack.append(i)
    return answer

# The smaller variants are the same with < and <= flipped.

def largest_rectangle(h):                              # bars; stack of indices, heights rising
    stack = deque()
    best = 0
    for i in range(len(h) + 1):                        # i == size is a sentinel of height 0
        cur = h[i] if i < len(h) else 0
        while stack and h[stack[-1]] >= cur:           # the top can grow no further right
            height = h[stack.pop()]
            left = -1 if not stack else stack[-1]      # nearest shorter bar on the left
            best = max(best, height * (i - left - 1))  # width between the two shorter bars
        stack.append(i)
    return best

Monotonic Stack, in JavaScript

function nextGreater(a) {
  const answer = new Array(a.length).fill(-1);
  const stack = [];   // indices, values decreasing bottom to top
  for (let i = 0; i < a.length; i++) {
    while (stack.length > 0 && a[stack[stack.length - 1]] < a[i]) {
      answer[stack.pop()] = a[i];
    }
    stack.push(i);
  }
  return answer;   // whatever is still on the stack keeps -1
}

function previousGreater(a) {
  const answer = new Array(a.length).fill(-1);
  const stack = [];
  for (let i = 0; i < a.length; i++) {
    while (stack.length > 0 && a[stack[stack.length - 1]] <= a[i]) stack.pop();
    if (stack.length > 0) answer[i] = a[stack[stack.length - 1]];
    stack.push(i);
  }
  return answer;
}

// The smaller variants are the same with < and <= flipped.

function largestRectangle(h) {                                // bars; stack of indices, heights rising
  const stack = []; let best = 0;
  for (let i = 0; i <= h.length; i++) {                       // i == size is a sentinel of height 0
    const cur = i < h.length ? h[i] : 0;
    while (stack.length > 0 && h[stack[stack.length - 1]] >= cur) {     // the top can grow no further right
      const height = h[stack.pop()];
      const left = stack.length === 0 ? -1 : stack[stack.length - 1];   // nearest shorter bar on the left
      best = Math.max(best, height * (i - left - 1));                   // width between the two shorter bars
    }
    stack.push(i);
  }
  return best;
}

Monotonic Stack, in Kotlin

fun nextGreater(a: IntArray): IntArray {
    val answer = IntArray(a.size) { -1 }
    val stack = ArrayDeque<Int>()   // indices, values decreasing bottom to top
    for (i in a.indices) {
        while (stack.isNotEmpty() && a[stack.last()] < a[i]) {
            answer[stack.removeLast()] = a[i]
        }
        stack.addLast(i)
    }
    return answer   // whatever is still on the stack keeps -1
}

fun previousGreater(a: IntArray): IntArray {
    val answer = IntArray(a.size) { -1 }
    val stack = ArrayDeque<Int>()
    for (i in a.indices) {
        while (stack.isNotEmpty() && a[stack.last()] <= a[i]) stack.removeLast()
        if (stack.isNotEmpty()) answer[i] = a[stack.last()]
        stack.addLast(i)
    }
    return answer
}

// The smaller variants are the same with < and <= flipped.

fun largestRectangle(h: IntArray): Int {                       // bars; stack of indices, heights rising
    val stack = ArrayDeque<Int>(); var best = 0
    for (i in 0..h.size) {                                       // i == size is a sentinel of height 0
        val cur = if (i < h.size) h[i] else 0
        while (stack.isNotEmpty() && h[stack.last()] >= cur) {     // the top can grow no further right
            val height = h[stack.removeLast()]
            val left = if (stack.isEmpty()) -1 else stack.last()  // nearest shorter bar on the left
            best = maxOf(best, height * (i - left - 1))            // width between the two shorter bars
        }
        stack.addLast(i)
    }
    return best
}

Write it yourself

Define largestRectangle(values) and return the area of the largest rectangle that fits under the histogram. It runs in your browser against this lesson's own 2 examples.

// Keep bars of increasing height on a stack. When a shorter bar arrives, each bar it pops has found its right edge.function largestRectangle(values) { return 0;}
6 linesTab indents. Escape, then Tab, leaves the editor. Ctrl-Enter runs (Cmd-Enter on a Mac).

    Remember

    • Every value is pushed once and popped at most once, so the nested loop is still O(n).
    • Next variants resolve on pop: the value doing the popping is the answer.
    • Previous variants resolve on push: after popping, the top is the answer or the stack is empty.

    Where this is used

    Operator precedence in expression parsersCompilers

    Dijkstra's shunting-yard algorithm, published in 1961, keeps an operator stack whose precedence never decreases from bottom to top inside a parenthesis group. An incoming operator pops and emits every stacked operator that binds more tightly, and equal-precedence ones too when the incoming operator is left-associative, which is this pop rule applied to precedence instead of value. The associativity half is where it goes wrong: pop on equal precedence for a right-associative operator and 2^3^2 comes out as (2^3)^2 = 64 instead of 2^(3^2) = 512.

    INDENT and DEDENT in Python's tokenizerLanguage runtimes

    CPython's tokenizer holds a stack of indentation columns that strictly increases. A line indented further pushes and emits INDENT, and a line indented less pops and emits one DEDENT per entry removed, stopping when the top matches the new column. The error 'unindent does not match any outer indentation level' is exactly the case where the popping runs past that column and no stacked level equals it.

    Windowed min and max filters in TCP BBRNetworking

    BBR needs the largest delivery rate and the smallest RTT seen in a recent window, and the Linux kernel tracks both in lib/win_minmax.c. A new sample that beats a stored candidate makes that candidate worthless forever, since the sample is both better and more recent, so it discards it - the same reasoning that lets the stack pop. The kernel keeps three candidates instead of a full deque, trading exactness for constant space.

    Convex hulls by monotone chainComputational geometry

    Andrew's monotone chain sorts the points, then walks them keeping a stack of hull vertices and popping any vertex the new point turns the wrong way around. A popped vertex lies inside the hull or flat on one of its edges and can never come back, so the scan costs O(n) after the sort. Graham scan is the same loop with a different sort order, and that is what GEOS runs behind PostGIS ST_ConvexHull: ConvexHull::grahamScan pops the stack while the last two kept points and the new one make a clockwise turn.

    Why it works this way

    One step can pop almost the whole array, so why is this O(n)?

    Look at the whole run, not the worst single step. The while loop at one index can strip nearly the whole stack, but every entry it removes was put there by an earlier index that already paid for it, so the cost is charged at push time and the total is bounded no matter how the pops clump. In 9 8 7 6 10 the first four steps pop nothing and the fifth pops four: that one step is collecting work the earlier steps banked.

    < or <= decides what happens to equal values

    nextGreater pops while a[top] < a[i], so an equal value never pops and the answer is the next strictly greater element. Flip that to <= and you get the next greater-or-equal, which is a different array. The histogram pops on >= on purpose: an equal bar evicts the earlier one and credits it a width that is too short, but the last bar of the equal run still spans the full width, so the maximum comes out right anyway.

    Why the stack holds indices and not values

    The value is always one lookup away as a[stack.last()], but a value cannot tell you where it came from. Next-greater needs the index to write the answer into the right slot, and the histogram needs it to measure width. After a pop, read the new top: that is the nearest shorter bar on the left, and because both boundaries are exclusive the rectangle spans i - left - 1 bars, not i - left.

    Whatever is left on the stack never found an answer

    Those entries were never beaten, so nothing to their right qualifies and next-greater leaves them at -1. The histogram cannot ignore them, because each one still owns a rectangle that runs to the end of the array. One extra iteration with a virtual bar of height 0 pops the stack clean and measures every leftover with its right edge at n, which is why that loop runs 0..h.size and not 0 until h.size.

    Read more

    Next up

    Stacks for Expressions

    Evaluate infix with two stacks

    Next lesson: Stacks for Expressions