Lesson 7 of 16 Stacks and Linked Lists

Monotonic Stack Pattern

Monotonic stack pattern for next greater element, daily temperatures and largest rectangle in histogram, with why each index is pushed and popped once.

35-45 min intermediate 0/16 lessons done
Course contents Lesson 7 of 16 · 0 done
On this page (8 sections)
  1. What you will learn
  2. Signals
  3. The idea
  4. Code
  5. Increasing or decreasing?
  6. Key takeaways
  7. Exercises
  8. Quiz

What you will learn

  • What a monotonic stack keeps and why it’s O(n).
  • Next greater element and daily temperatures.
  • Largest rectangle in a histogram, the classic hard version.

Signals

  • “Next greater / next smaller / previous greater element”.
  • “How many days until…”, “how far can this bar extend?”
  • Spans, visibility, or areas bounded by the nearest smaller element.

The idea

Scan left to right and keep a stack of indices still waiting for their answer. When a new value resolves some of them (it’s greater than the values on top), pop and answer them. The remaining stack is always monotonic, which is where the name comes from. Each index is pushed once and popped at most once: O(n).

Code

"""Monotonic stack: next greater element, daily temperatures, largest rectangle."""


def next_greater(nums):
    out = [-1] * len(nums)
    stack = []  # indices whose next greater element we haven't found yet (values decreasing)
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            out[stack.pop()] = x
        stack.append(i)
    return out


def daily_temperatures(temps):
    out = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            out[j] = i - j
        stack.append(i)
    return out


def largest_rectangle(heights):
    best, stack = 0, []  # indices with increasing heights
    for i, h in enumerate(heights + [0]):  # trailing 0 flushes the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best


if __name__ == "__main__":
    print(next_greater([2, 1, 2, 4, 3]))
    print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
    print(largest_rectangle([2, 1, 5, 6, 2, 3]))

Output:

[4, 2, 4, -1, -1]
[1, 1, 4, 2, 1, 1, 0, 0]
10
  • Next greater: the stack holds indices with decreasing values. Values left on the stack at the end have no greater element (-1).
  • Daily temperatures: same scan, but store the distance i - j.
  • Largest rectangle: keep increasing heights. When a lower bar arrives, each popped bar can’t extend further right; its left limit is the new stack top. A trailing 0 flushes the stack at the end. Answer 10 is bars 5 and 6 at height 5.

Increasing or decreasing?

  • Looking for the next greater element → keep a decreasing stack (pop smaller values).
  • Looking for the next smaller element → keep an increasing stack.

The deque version of this idea solves sliding window maximum.

Practise: monotonic stack problems, and the plain stack section for bracket matching.

Key takeaways

  • The stack holds indices still waiting for an answer; new elements resolve them.
  • Decreasing stack for next greater, increasing stack for next smaller.
  • Each index is pushed and popped once, so O(n).
  • Largest rectangle: popping a bar fixes both its right and left limits.

Exercises

  1. Next greater element in a circular array (loop twice over indices).
  2. Stock span problem: for each day, how many consecutive previous days had price ≤ today.
  3. Maximal rectangle in a binary matrix using largest_rectangle per row.

Quiz

  1. Which stack order do you keep to find the next greater element?
  2. Why is the algorithm O(n) despite the inner while loop?
  3. Why append a 0 to heights in largest rectangle?
Show answers
  1. Decreasing (from bottom to top), popping smaller values when a bigger one arrives.
  2. Each index is pushed once and popped at most once, so all inner loop iterations add up to at most n.
  3. A final bar of height 0 is lower than everything, which pops and evaluates every remaining bar.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).