Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 225 ยท Stacks and Queues

Monotonic Stack

Learn the monotonic stack in Python: next greater element, daily temperatures, stock span and largest rectangle in a histogram, with traces and O(n) analysis.

Some problems ask, for every item in a list, a question about its nearest neighbor with a certain property: "Which is the next day that is warmer than today?", "How far back do I have to go to find a higher price?", "What is the first taller bar to my right?" The obvious answer is a nested loop that scans outward from every item, which is O(nยฒ).

A monotonic stack answers all of these questions in one pass and O(n) time. It is an ordinary stack with one extra rule: before you push an item, you pop everything that would break the order (always increasing or always decreasing) from the top. The popped items are exactly the ones whose question you have just answered.

The idea

Take the next greater element problem: for each number, find the first number to its right that is strictly larger, or -1 if there is none.

Walk left to right and keep a stack of indexes whose answer is still unknown. Those items are waiting for something bigger. When a new number arrives:

  1. While the number on top of the stack is smaller than the new number, the new number is its answer. Pop it and record the answer.
  2. Push the new number's index. It now waits for its own answer.

Because we pop every smaller item before pushing, the values waiting on the stack are always non-increasing from bottom to top. That ordering is what the word "monotonic" means here.

TEXT
nums = [4, 5, 2, 10, 8]

i=0  4:  stack empty                      push 4        stack (values): [4]
i=1  5:  4 < 5 -> answer[4] = 5, pop      push 5        stack: [5]
i=2  2:  5 > 2, nothing to pop            push 2        stack: [5, 2]
i=3 10:  2 < 10 -> answer[2] = 10, pop
         5 < 10 -> answer[5] = 10, pop    push 10       stack: [10]
i=4  8:  10 > 8, nothing to pop           push 8        stack: [10, 8]
end:     10 and 8 never found a bigger value -> -1

The stack stores indexes, not values. The index gives you the value (nums[i]) and also the position, which you need for distances such as "how many days until a warmer one".

Brute force first

For each position scan to the right until you meet a bigger value. In the worst case (a descending list) every scan runs to the end, so the total is about nยฒ/2 comparisons.

Python Next greater element: brute force vs stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a descending list of 1,000 numbers the brute force does the maximum amount of work, while the stack version does one push per item and never pops.

Why it is O(n)

The while loop sits inside a for loop, which looks quadratic. It is not: every index is pushed exactly once and popped at most once. Over the whole run there are at most n pushes and n pops, so the total work is at most 2n operations. This is an example of amortized analysis: one iteration may pop many items, but those pops were "paid for" by earlier pushes.

Space is O(n) for the stack in the worst case (a strictly decreasing input leaves everything on the stack) plus O(n) for the answers.

Variation 1: Daily Temperatures (distance to the next warmer day)

Problem. Given daily temperatures, return for each day how many days you must wait for a warmer one, or 0 if that never happens.

It is the same algorithm. Instead of storing the value as the answer, store the index difference today - colder_day.

Python Daily temperatures

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the first answer by hand: day 0 (73) waits one day for 74, day 2 (75) waits four days for 76, and the last day (73) never sees a warmer day, so it stays 0.

The four neighbor questions

The same machine solves four related questions. Only two choices change: which side you look at, and whether you pop larger or smaller items.

Question Pop while the top is... Where the answer comes from
Next greater element to the right smaller than the new item the new item (assigned to each popped index)
Next smaller element to the right larger than the new item the new item (assigned to each popped index)
Previous greater element to the left smaller than or equal to the new item the item left on top after popping
Previous smaller element to the left larger than or equal to the new item the item left on top after popping

All four scan left to right. For the "previous" questions, the answer for the new item is whatever is left on top after popping. For the "next" questions, the answer is the new item itself, assigned to everything it pops.

Variation 2: Stock Span

Problem. For each day, the span is the number of consecutive days up to and including today whose price was less than or equal to today's price.

That is a "previous greater element" question: find the nearest earlier day with a strictly higher price. The span is the distance to it (or the whole prefix if there is none).

TEXT
prices = [100, 80, 60, 70, 60, 75, 85]

day 0  100: stack empty                  span 1
day 1   80: top 100 > 80, keep           span 1  (1 - 0)
day 2   60: top 80 > 60, keep            span 1
day 3   70: pop 60 (<= 70); top 80       span 2  (3 - 1)
day 4   60: top 70 > 60, keep            span 1
day 5   75: pop 60, pop 70; top 80       span 4  (5 - 1)
day 6   85: pop 75, pop 80; top 100      span 6  (6 - 0)
Python Stock span

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Using -1 as the "no previous greater" index makes the formula day - previous_higher work for every case, including when the stack is empty.

Variation 3: Largest Rectangle in a Histogram

This is the famous harder problem. You have bars with heights h[0..n-1], each of width 1. Find the area of the largest rectangle that fits entirely inside the bars.

Key observation. The best rectangle has some bar i as its limiting height. It extends left and right until it hits a bar that is shorter than h[i]. So for each bar we need:

  • the nearest shorter bar on the left (index L),
  • the nearest shorter bar on the right (index R),

and the rectangle has height h[i] and width R - L - 1.

Brute force. For each bar expand left and right: O(nยฒ).

Monotonic stack. Keep an increasing stack of bar indexes. When a bar is shorter than the top, the top bar's rectangle can no longer grow to the right: the new bar is its right boundary R, and the element beneath it on the stack is its left boundary L. Pop it and compute its area. A sentinel bar of height 0 at the end flushes everything left on the stack.

TEXT
heights = [2, 1, 5, 6, 2, 3] + sentinel 0

i=0 h=2: push                           stack (heights): [2]
i=1 h=1: pop bar 2: L=-1, R=1           width 1, area 2
         push                           stack: [1]
i=2 h=5: push                           stack: [1, 5]
i=3 h=6: push                           stack: [1, 5, 6]
i=4 h=2: pop bar 6: L=2, R=4            width 1, area 6
         pop bar 5: L=1, R=4            width 2, area 10   <- best
         push                           stack: [1, 2]
i=5 h=3: push                           stack: [1, 2, 3]
i=6 h=0: pop bar 3: L=4, R=6            width 1, area 3
         pop bar 2: L=1, R=6            width 4, area 8
         pop bar 1: L=-1, R=6           width 6, area 6

The width formula is R - L - 1, where R is the index of the bar that caused the pop and L is the new top after popping (or -1 if the stack is empty).

Python Largest rectangle in a histogram

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that heights + [0] creates a new list. That is fine here. In the sentinel step the index right equals len(heights), and it is pushed onto the stack but never used to look up a height afterwards.

When bars have equal heights, decide on > or >= consistently. With > (as above), equal bars stay on the stack, and the last equal bar later computes the full-width area, because the left boundary is then the bar below the whole group. The [3, 3, 3] test is a good check that your version handles ties.

Bonus: the same trick on a grid

"Maximal rectangle of 1s in a binary matrix" turns each row into a histogram of consecutive 1s above it, then calls the function above once per row. See also matrices.

Common mistakes

  • Pushing values instead of indexes, then being unable to compute distances or widths.
  • Using < vs <= inconsistently. Decide whether equal values pop each other, and test with duplicates such as [2, 2, 2].
  • Forgetting the leftovers. In "next greater", items still on the stack at the end have no answer; the pre-filled -1 or 0 handles that. In the histogram, the sentinel bar handles it.
  • Calling .pop() on an empty stack. Always test while stack and ... in that order.
  • Using it where the neighbor is not "nearest". The monotonic stack finds the nearest element with a property. For "the largest within k positions" you want a monotonic queue.

When to use it

Reach for a monotonic stack when the problem says "next", "previous", "nearest", "span", "visible" or "until", asks for a per-item answer, and the brute force scans outward from every item. It reduces O(nยฒ) to O(n) time with O(n) extra space.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a monotonic stack guarantee about the values it holds?

    Before pushing, you pop everything that would break the chosen order, so the stack is always increasing or always decreasing.
  2. 2. The next-greater-element code has a while loop inside a for loop. What is its time complexity?

    Each index is pushed once and popped at most once, so the total number of operations is at most 2n.
  3. 3. Why does the Daily Temperatures solution store indexes on the stack instead of temperatures?

    The answer is today - colder_day. With only the temperature you could not recover the day.
  4. 4. In the largest-rectangle algorithm, what happens when a bar is shorter than the bar on top of the stack?

    The shorter bar is the right boundary for the taller bar on top, which can no longer extend further right, so its best rectangle is final.
  5. 5. For the stock-span problem, which classic question is being answered for each day?

    The span is the distance back to the nearest earlier day with a strictly higher price.

Summary

  • A monotonic stack is a stack that keeps its items in one consistent order by popping violators before each push.
  • It answers "nearest greater or smaller neighbor" questions for every item in O(n) total time, because each index is pushed and popped at most once.
  • Store indexes so you can compute distances and widths.
  • "Next" questions assign the answer to the items being popped; "previous" questions read the answer from the item left on top.
  • Largest rectangle in a histogram uses an increasing stack and a sentinel bar of height 0.
  • When the window size matters, use a monotonic queue instead.

Next: Queues