TechPrep
Searching and orderingReadLabPracticeCheck

Monotonic stack

Keep a stack whose values only decrease (or increase) so each element finds its next greater or smaller neighbour in one pass.

Daily Temperatures. For each day in temps, return how many days until a warmer temperature, or 0 if none comes.

Signals that point here

The idea

Keep indices of days still waiting for a warmer day. Their temperatures are non-increasing from bottom to top, because a warmer day would already have resolved everything colder beneath it.

When today is warmer than the top, the top's wait is over: pop it and record i - j. Keep popping while that holds, then push today. Every index is pushed once and popped at most once.

def daily_temperatures(temps: list[int]) -> list[int]:
    answer = [0] * len(temps)
    stack: list[int] = []            # indices; temps non-increasing upward
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

Complexity

O(n) time (each index pushed and popped at most once) and O(n) space.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. For each element, find the next greater element in a circular array.
  2. Find the largest rectangle in a histogram.
  3. Remove k digits from a number string to make it as small as possible.

Check yourself

Why is the stack monotone?

Any warmer day would already have popped every colder day below it, so the survivors are non-increasing.

Why is the nested loop linear overall?

Each index is pushed once and popped at most once, so total pops are at most n.

Saved in this browser.