Daily Temperatures

You are given a list temperatures where temperatures[i] is the reading on day i.

Return a list answer of the same length, where answer[i] is the number of days you have to wait after day i until a day with a strictly higher temperature. If no later day is warmer, answer[i] is 0.

Example 1

Example 2

Example 3

Constraints

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

Pattern Path · Stacks · problem 45 of 169

Start simple

For every day, scan forward until a warmer day appears: O(n²) time when the readings stay flat or fall for a long time.

The key idea

Walk through the days from left to right, keeping a stack of the indices of days that have not yet found a warmer day. A key invariant holds: the temperatures of the days on the stack never increase from bottom to top. If a warmer day had been pushed above a colder one, it would have settled the colder one first.

When day i arrives, compare it with the day on top of the stack. While the top day is strictly colder, day i is the first warmer day it has seen (every day in between was popped earlier, or was not warmer). So pop it and set answer[top] = i - top. Stop when the stack is empty or the top is at least as warm, then push i.

Days still on the stack at the end never see a warmer day, so their answer stays 0.

Every index is pushed once and popped at most once, so the total work is linear even though a single day may pop many others. This is the monotonic stack pattern: it answers "next greater element" questions for every position in one pass.

Complexity

• Time: O(n)
• Space: O(n)

Python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        waiting = []  # indices of days with no warmer day yet; temperatures non-increasing
        for i, temp in enumerate(temperatures):
            while waiting and temperatures[waiting[-1]] < temp:
                day = waiting.pop()
                answer[day] = i - day
            waiting.append(i)
        return answer

JavaScript

var dailyTemperatures = function(temperatures) {
  const answer = new Array(temperatures.length).fill(0);
  const waiting = []; // indices of days with no warmer day yet; temperatures non-increasing
  for (let i = 0; i < temperatures.length; i++) {
    while (waiting.length > 0 && temperatures[waiting[waiting.length - 1]] < temperatures[i]) {
      const day = waiting.pop();
      answer[day] = i - day;
    }
    waiting.push(i);
  }
  return answer;
};

What the interviewer is checking

The interviewer is checking whether you recognise a next-greater-element problem and can use a monotonic stack, and whether you can argue why its running time is linear.

Mistakes to avoid

• Pushing temperatures instead of indices, so the waiting time cannot be computed.
• Popping on equal temperatures; the problem asks for strictly warmer days.
• Assuming nested loops are O(n²) here; each index is popped at most once, so the total is O(n).

Follow-ups to expect

• Can you do it with O(1) extra space? (Scan right to left, jump using answers.)
• How would you find the previous warmer day instead? (Same stack, other direction.)
• What if readings arrive as a stream? (Settle waiting days as each reading arrives.)

In real software

Stock analysis tools compute "days until price exceeds today" and span indicators this way, and the same monotonic stack drives histogram and skyline computations in graphics and layout engines.

Practice next