Skip to content
BytePatterns

Monotonic Stack

Stacks & Queues: lesson 5 of 5

Keep the stack ordered and every item waits only once.

Lesson 5 of 5 · 6 min

Monotonic Stack

Step 1 of 13

Each roof wants the first taller roof to its right. Brute force compares every pair — O(n²).

The Idea

Hold a stack whose values only ever decrease from bottom to top. A new value pops everything smaller than itself — and it is the answer for each one it pops. Since every index is pushed once and popped once, a search that looks O(n²) finishes in O(n).

Real-World Example

A row of rooftops, each wanting to know the first taller roof to its east. Short roofs pile up unanswered behind one another; the moment a tower finally appears it settles the question for all of them in a single sweep.

The Code

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                            # indexes, values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x       # x answers everyone smaller
        stack.append(i)
    return result                         # -1 means nothing bigger ahead

print(next_greater([2, 1, 3]))            # [3, 3, -1]
print(next_greater([5, 4, 3]))            # [-1, -1, -1]

Your turn

Put the steps in the right order.

  1. Push the current index onto the stack
  2. Read the next value in the array
  3. Start with an empty stack and a result array of -1
  4. Pop every index whose value is smaller and record the answer

Mini quiz

1 / 3

What stays true of the values held in the stack?