The monotonic stack pattern

Stacks and queues Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
vals = [4, 1, 3, 2, 5]
next_bigger = [-1] * len(vals)
stack: list[int] = []
for i, v in enumerate(vals):
    while stack and vals[stack[-1]] < v:
        next_bigger[stack.pop()] = v
    stack.append(i)
print(next_bigger)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [5, 3, 5, 5, -1]

Right: each value's first bigger value to its right.

Items wait on the stack until something bigger arrives, which is when their answer is written.

Why not the others?
  • B [5, 3, 5, 5, 5]. Nothing comes after 5, so it keeps -1.
  • C [-1, 3, 5, 5, -1]. 4 is answered when 5 arrives.

30-second answer

A monotonic stack keeps its items in increasing or decreasing order. When a new item would break the order, you pop items until it fits, and each pop is the moment a popped item learns its answer: the new item is its next bigger (or smaller) neighbour. Each item is pushed and popped at most once, so the whole scan is O(n).

Practise saying it · 45 s. No recording, just a timer

Explain the monotonic stack.

Say your answer out loud, then check which of these points you covered:

  • Stack kept in order
  • Pops answer questions
  • O(n) total

Deep dive

Next greater item, next warmer day, stock-price spans and the largest rectangle under a skyline all use it.

Store indexes, not values, when the answer is a distance or width.

Decide strict versus non-strict comparison from how ties should behave.

Common mistakes

  • Using the wrong direction (increasing vs decreasing) for the question.
  • Calling it O(n²) because of the inner while loop.

Senior take & follow-ups

Say 'each pop answers a question' — it explains both correctness and cost.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you find the previous smaller item instead?

    Show hint

    Scan left to right; after popping bigger items, the stack top is the previous smaller one.

  2. What is a monotonic deque?

    Show hint

    The same idea with pops from the front too, used for sliding-window maximums.

What each operation costs: Stack · Queue · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.