DEV Community

Sh Raj
Sh Raj

Posted on

One Stack, Ten Problems: The Monotonic Stack Pattern Every Interview Candidate Should Know

You have an array. For each element, find the next element to its right that is bigger than it. The brute-force answer is two nested loops: O(n²). The interview answer is one pass with a stack: O(n). And once you see the pattern, you will recognise it in at least ten classic problems.

The idea in one paragraph

A monotonic stack keeps its elements in sorted order — increasing or decreasing. You walk the array once. Each element is pushed once and popped at most once, which is why the whole thing is O(n). The trick is what a pop means: when a new element breaks the order, it resolves every element waiting on the stack that it beats.

The cleanest first example is LeetCode 739, Daily Temperatures: for each day, how many days until a warmer one?

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    stack = []  # indices of days waiting for a warmer day
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer
Enter fullscreen mode Exit fullscreen mode

The stack holds indices in decreasing temperature order. A day sits on the stack, unresolved, until a warmer day arrives and pops it. That warmer day is exactly the answer for every day it pops. Nothing is ever revisited.

The four variants

Flip two choices — the comparison, and which direction you scan — and you get four tools:

Scan Comparison Answers
Left to right pop while stack top < current Next greater element
Left to right pop while stack top > current Next smaller element
Right to left pop while stack top < current Previous greater element
Right to left pop while stack top > current Previous smaller element

Most problems are one row of this table plus a small twist. Learn the table and you stop memorising solutions.

The practice ladder

Work these in order. Each one adds exactly one new idea:

  1. 496. Next Greater Element I (Easy) — the pure form. Build a map from value to next greater, then answer the queries.
  2. 739. Daily Temperatures (Medium) — same shape, but record the index distance instead of the value.
  3. 503. Next Greater Element II (Medium) — the array is circular. Run the same loop over 2n indices with i % n.
  4. 901. Online Stock Span (Medium) — collapse consecutive days the current price dominates. Store (price, span) pairs on the stack and accumulate spans as you pop.
  5. 402. Remove K Digits (Medium) — a greedy deletion: pop while the top is bigger than the current digit and you still have deletions left.
  6. 456. 132 Pattern (Medium) — scan right to left with a decreasing stack, tracking the largest valid "2" seen so far.
  7. 84. Largest Rectangle in Histogram (Hard) — the boss fight. For each bar, the stack finds how far left and right it can extend before hitting a shorter bar. Area = height × width. Add a sentinel zero at the end to flush the stack.
  8. 85. Maximal Rectangle (Hard) — build a histogram row by row from the matrix, then run problem 7 on each row.
  9. 42. Trapping Rain Water (Hard) — the stack version: when a bar pops, the water above it is bounded by the new stack top on the left and the current bar on the right.
  10. 1944. Number of Visible People in a Queue (Hard) — each person sees everyone until the first taller person, plus that taller person. A decreasing stack counts exactly that.

How to spot it in an interview

Listen for the shape of the question, not the story: "next greater / smaller", "how many days until", "span", "how far can this extend", "first element that breaks the pattern". If the question is about each element's relationship to its nearest bigger or smaller neighbour, reach for the stack before you reach for the nested loop.

Two practical tips. First, store indices, not values — you almost always need the position for the answer or the width. Second, decide the comparison by asking what a pop should mean: if popping should resolve "I found something bigger", pop while the top is smaller.

The pattern is small enough to learn in an afternoon and shows up often enough to pay for that afternoon many times over. Do the ladder in order, and by problem 7 you will be writing the template from memory.

Top comments (0)