Daily Temperatures

The problem

The list temperatures holds one temperature for each day. Return a list of the same length that says, for each day, how many days you have to wait from that day until a strictly warmer one. If no later day is warmer, that day's entry is 0. A later day with the same temperature does not count as warmer. An empty list returns an empty list.

What to write

function solve(temperatures: number[]): number[]

Input
temperatures = [73,74,75,71,69,72,76,73]

Output
[1,1,4,2,1,1,0,0]

Input
temperatures = [30,40,50,60]

Output
[1,1,1,0]

Constraints

0–10,000 integer temperatures within -100 to 200.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 10,000 days. Looking ahead from every day until you find a warmer one takes about 50 million steps when the temperatures keep falling. Try to answer every day in a single pass from left to right.

2. Hint 2: Ask a smaller question

   Read 80, 75, 71, 69 and then 72. Which earlier days get their answer from the 72, and in what order do you check them? Once you see that the 75 is still waiting, do you need to check the 80 at all?

3. Hint 3: Name the pattern

   For each day you want the next day that is warmer. The days still waiting never get warmer from oldest to newest, and a new day answers them newest first. A stack whose values only ever go one way like this is a monotonic stack. Read the lesson on monotonic stack.

4. Hint 4: State the invariant

   The stack holds the positions of the days that have not met a warmer day yet, oldest at the bottom. Their temperatures never rise from bottom to top, so the coolest waiting day is always on top.

5. Hint 5: Sketch the pseudocode

   Fill the answer with zeros and start an empty stack of positions. For each day i: while the stack is not empty and day i is warmer than the day on top, pop that day j and set its answer to i minus j. Then push i. Return the answer.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Keep indices on a stack whose temperatures never rise. A warmer day resolves all cooler stack entries by subtracting their index from the current index.

The slow way

For each day, look ahead one day at a time until you find a warmer one, and count the steps. It is correct, but when the temperatures keep falling, every day scans all the days after it. With 10,000 days that is about 50 million comparisons.

The insight

Turn the question around. Instead of every day searching ahead, let each new day answer the earlier days that were waiting for it. The waiting days never get warmer from oldest to newest, so a new day checks them from the newest backwards and stops at the first one that is not cooler than it.

Step by step

1. Start every answer at 0 and keep a stack of the days still waiting. A day that never meets a warmer one must answer 0, so that is the starting value. The stack holds the positions of the days with no answer yet, newest on top.
2. While today is warmer than the day on top, that day's wait is over. The day on top is the coolest one waiting. If today is not warmer than it, today is not warmer than any of the others either, so the checking can stop there.
3. Take that day off the stack and record how long it waited. The stack stores positions, so the wait is today's position minus that day's. Today is its first warmer day: an earlier warmer day would already have taken it off.
4. Today now waits on top of the stack. Every day left on the stack is at least as warm as today, so with today on top the temperatures still never rise from bottom to top.
5. Days still on the stack never met a warmer day and keep their 0. Nothing after them was warmer, or it would have taken them off the stack. Their answers were set to 0 at the start, so nothing more has to be done.

The same numbered steps are the comments in each solution.

function solve(temperatures) {
  // 1. Start every answer at 0 and keep a stack of the days still waiting
  const out = Array(temperatures.length).fill(0),
    stack = [];
  for (let i = 0; i < temperatures.length; i++) {
    // 2. While today is warmer than the day on top, that day's wait is over
    while (
      stack.length &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      // 3. Take that day off the stack and record how long it waited
      const j = stack.pop();
      out[j] = i - j;
    }
    // 4. Today now waits on top of the stack
    stack.push(i);
  }
  // 5. Days still on the stack never met a warmer day and keep their 0
  return out;
}

function solve(temperatures: number[]): number[] {
  // 1. Start every answer at 0 and keep a stack of the days still waiting
  const out = Array(temperatures.length).fill(0),
    stack = [];
  for (let i = 0; i < temperatures.length; i++) {
    // 2. While today is warmer than the day on top, that day's wait is over
    while (
      stack.length &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      // 3. Take that day off the stack and record how long it waited
      const j = stack.pop()!;
      out[j] = i - j;
    }
    // 4. Today now waits on top of the stack
    stack.push(i);
  }
  // 5. Days still on the stack never met a warmer day and keep their 0
  return out;
}

def solve(temperatures):
    # 1. Start every answer at 0 and keep a stack of the days still waiting
    out = [0] * len(temperatures)
    stack = []
    for i, temperature in enumerate(temperatures):
        # 2. While today is warmer than the day on top, that day's wait is over
        while stack and temperature > temperatures[stack[-1]]:
            # 3. Take that day off the stack and record how long it waited
            j = stack.pop()
            out[j] = i - j
        # 4. Today now waits on top of the stack
        stack.append(i)
    # 5. Days still on the stack never met a warmer day and keep their 0
    return out

Example 1, traced

Input
temperatures = [73,74,75,71,69,72,76,73]

Output
[1,1,4,2,1,1,0,0]

Why it works

A day leaves the stack at the first later day that is warmer than it: an earlier warmer day would have removed it already. The waiting temperatures never rise toward the top, so a new day that is not warmer than the top is not warmer than anything below it, and no waiting day is missed.

Time and space

Time O(n), extra space O(n). Each day is pushed once and popped at most once, so the inner loop runs at most n times in total, whatever the temperatures are: O(n) time. When the temperatures keep falling, every day waits on the stack at once: O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Pop in a loop, not with a single test. One warm day can end several waits. With a single test, example 1 gives 0 to the days with 75 and 71, where the answers are 4 and 2.
• The comparison is strictly warmer. With "warmer or equal", the list 30, 30 would answer 1 for its first day, and the right answer is 0.
• Record the wait, not the position of the warmer day. In example 1 the 75 at position 2 meets the 76 at position 6, and its answer is 6 minus 2, which is 4.

Pattern

Monotonic stack. Builds on Valid Parentheses.

Keep going