LeetCode 739 · Stack

Daily Temperatures, explained with a picture

Waiting for a warmer day.

MediumStack
▶ Watch it step by step

The problem

Given daily temperatures, for each day say how many days you must wait for a warmer day. Write 0 if a warmer day never comes.

Input:  [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

Picture it

Picture each day as a person waiting in a stack, holding a thermometer. A new day arrives. Every waiting person cooler than today finally gets their warmer day: they step off the stack and write down how long they waited. Then today joins the stack and waits too. People still on the stack at the end never got a warmer day.

How to recognise it

  • For each position you need the next position to its right that is bigger (or smaller). This is the "next greater element" family.
  • The answer for one day is decided by a later day, so days must wait until their answer arrives.
  • When a warm day arrives, it answers every cooler day still waiting, starting with the most recent one. Waiting items that are resolved newest-first suggest a stack.
  • Up to 10^5 days, so comparing every pair of days is too slow.

Start with brute force

For each day, walk forward until you find a warmer day, and record the distance.

def daily_brute(temps):
    n = len(temps)
    wait = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temps[j] > temps[i]:
                wait[i] = j - i
                break
    return wait

Time is O(n²) in the worst case and extra space is O(1) besides the output. A long cold spell at a constant 30 degrees never finds a warmer day, so every day scans to the end: with n = 10^5 that is about 5 × 10^9 comparisons.

From brute force to the idea

  1. Find the waste. The scans overlap. If day 3 at 71 degrees and day 4 at 69 degrees both wait, day 5 at 72 degrees is the answer for both, yet the brute force finds it twice in two separate walks.
  2. Keep the unanswered days. Walk once from left to right and hold a stack of positions whose warmer day has not arrived yet.
  3. The stack stays in order. A day only stays on the stack if no later day was warmer, so from bottom to top the temperatures never rise: the coolest waiting day is on top.
  4. Resolve from the top. When day i with temperature t arrives, pop every waiting day j with temps[j] < t and set wait[j] = i - j. Stop at the first day that is at least as warm; everything below it is warmer still, so they keep waiting too.
  5. Then wait yourself. Push i. Days still on the stack at the end never got warmer and keep their 0.

This is the key idea: a stack of unanswered days, coolest on top, lets each new day answer all the days it beats in one sweep.

The key idea

A “monotonic stack” keeps waiting days in decreasing temperature. Each day is pushed and popped once: O(n).

Python solution

def daily_temperatures(temps):
    wait = [0] * len(temps)
    stack = []                      # days still waiting, coolest on top
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            wait[j] = i - j          # day j finally got warmer
        stack.append(i)
    return wait

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): a forward scan from every dayO(1) besides the output
Monotonic stack (shown code)O(n): each position is pushed once and popped at most once, so the while loop runs at most n times in totalO(n): a non-rising run of days all wait on the stack

Edge cases

  • Empty list: returns []. LeetCode promises at least one day.
  • A single day ([50]): returns [0].
  • Equal temperatures ([70, 70]): returns [0, 0]. The comparison is strict, so an equally warm day does not count, and the first 70 keeps waiting under the second.
  • Equal then warmer ([70, 70, 75]): returns [2, 1, 0]; the 75 pops both days.
  • Rising ([30, 40, 50, 60]): [1, 1, 1, 0]. Each day is popped by the next one.
  • Falling ([60, 50, 40, 30]): all zeros, and the stack grows to n items.

Common mistakes

  • Storing temperatures on the stack instead of positions. You need the position to compute i - j and to write into wait[j].
  • Popping with <= instead of <. A day of equal temperature would then answer the earlier day, which the problem forbids.
  • Starting wait as an empty list and only writing answers for popped days. Days still on the stack at the end then have no entry; filling the list with 0 up front covers them.
Your turn: since the last warmer day

For each day, return how many days ago the most recent strictly warmer day was, or 0 if there was none. For [73, 74, 75, 71, 69, 72, 76, 73] the answer is [0, 0, 0, 1, 1, 3, 0, 1]. Describe your approach, then write it if you like.

Compare with our answer

Now the answer lies to the left, so each day reads it from the stack at the moment it arrives. Pop every earlier day that is not warmer (they can never be the answer for any later day either, because today is at least as warm and closer). Whatever is left on top is the most recent warmer day.

def since_warmer(temps):
    out = [0] * len(temps)
    stack = []                      # positions, warmest at the bottom
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] <= t:
            stack.pop()
        out[i] = i - stack[-1] if stack else 0
        stack.append(i)
    return out

Time O(n), space O(n).

A strong answer mentions: why popped days are useless for every later day, why the pop uses <= here (a day of equal temperature is not strictly warmer), and that the answer is read after popping and before pushing.

Check what stuck

1. For each day's share price, you must find how many days until the price first drops below today's. Which approach fits best?

2. Why is the shown code O(n) even though it has a while loop inside a for loop?

3. A learner writes while stack and temps[stack[-1]] <= t:. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.