🎓 A1Learner
🔍
0 of 47 lessons completed

The Monotonic Stack Pattern

A monotonic stack is a stack that stays in one order while items are added. The order is rising or falling, never mixed.

Spot the signal

A problem asks for the next greater item for each position. The naive way scans forward from every item.

nums = [2, 1, 5, 3]
for i, value in enumerate(nums):
    found = "none"
    for later in nums[i + 1:]:
        if later > value:
            found = later
            break
    print(value, "->", found)

The template

Keep a stack of positions with rising values. A bigger value settles every smaller value below it.

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            result[stack.pop()] = value
        stack.append(i)
    return result
print(next_greater([2, 1, 5, 3]))

Worked problem: warmer days

Count the days until a warmer day for each day. The stack holds days still waiting for warmth.

temps = [73, 74, 75, 71, 69, 72, 76, 73]
wait = [0] * len(temps)
stack = []
for i, temp in enumerate(temps):
    while stack and temps[stack[-1]] < temp:
        day = stack.pop()
        wait[day] = i - day
    stack.append(i)
print(wait)

Example

def previous_smaller(nums):
    result = []
    stack = []
    for value in nums:
        while stack and stack[-1] >= value:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(value)
    return result
print(previous_smaller([3, 1, 4, 2]))

Key points

  • Monotonic: ordered in one direction, rising or falling.
  • Use a monotonic stack to find the next greater or smaller item for each position.
  • Pop while the top item breaks the order, then push the new item.
  • Each item is pushed once and popped once, so the pass is fast.
  • A monotonic stack turns a next-item question into one pass.

The code keeps a rising stack of values seen so far. Values that are not smaller are popped before each new value. The top that survives is the previous smaller value.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

What order does a monotonic stack keep?