Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Daily Temperatures

For each day, find how many days until a warmer one. A monotonic stack of days still waiting for an answer solves it in a single O(n) pass.

Updated Short read: 5 min read

Approaches at a glance

ApproachTimeSpace
Brute forceO(n²)O(1)
Monotonic stackO(n)O(n)

The problem

Given a list of daily temperatures, return a list of the same length in which each entry says how many days you would have to wait, after that day, for a warmer temperature. If no later day is warmer, the entry is 0.

[73, 74, 75, 71, 69, 72, 76, 73]   →  [1, 1, 4, 2, 1, 1, 0, 0]
[30, 40, 50, 60]                   →  [1, 1, 1, 0]
[90, 80, 70]                       →  [0, 0, 0]

In the first example, day 2 (75°) waits four days for day 6 (76°). A day with the same temperature does not count as warmer.

The space figures below do not count the list of answers that is returned.

Approach 1: brute force

From each day, scan forwards until a warmer day turns up.

JavaScript

function dailyTemperaturesBruteForce(temperatures) {
  const waits = new Array(temperatures.length).fill(0);
 
  for (let day = 0; day < temperatures.length; day++) {
    for (let later = day + 1; later < temperatures.length; later++) {
      if (temperatures[later] > temperatures[day]) {
        waits[day] = later - day;
        break;
      }
    }
  }
  return waits;
}

Python

def daily_temperatures_brute_force(temperatures):
    waits = [0] * len(temperatures)
 
    for day in range(len(temperatures)):
        for later in range(day + 1, len(temperatures)):
            if temperatures[later] > temperatures[day]:
                waits[day] = later - day
                break
    return waits

Time O(n²): a list of steadily falling temperatures makes every scan run to the end. Space O(1).

Approach 2: monotonic stack

The brute force asks, on each day, "when will it be warmer?", and goes looking. Turn the question round: on each day, ask "which earlier days have been waiting for a temperature like this one?".

Keep a stack of the days that have not found a warmer day yet. When a new day arrives:

  1. While the day on top of the stack is cooler than today, today is its answer. Pop it and record the gap.
  2. Push today. It now waits for its own warmer day.

JavaScript

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

Python

def daily_temperatures(temperatures):
    waits = [0] * len(temperatures)
    waiting = []  # indexes of days with no warmer day yet
 
    for day, temperature in enumerate(temperatures):
        while waiting and temperatures[waiting[-1]] < temperature:
            earlier = waiting.pop()
            waits[earlier] = day - earlier
        waiting.append(day)
    return waits

Days still on the stack when the loop ends never found a warmer day. Their entries keep the 0 they were created with.

The stack stores indexes, because the answer is a number of days. The temperature is always available through the index.

Walkthrough

[73, 74, 75, 71, 69, 72, 76, 73]. The stack is shown as temperatures for readability; the code stores the day numbers.

Day (temp) Popped: answer recorded Stack after
0 (73) 73
1 (74) Day 0: waits 1 74
2 (75) Day 1: waits 1 75
3 (71) 75, 71
4 (69) 75, 71, 69
5 (72) Day 4: waits 1. Day 3: waits 2 75, 72
6 (76) Day 5: waits 1. Day 2: waits 4 76
7 (73) 76, 73

Days 6 and 7 are left on the stack, so their answers stay 0. The result is [1, 1, 4, 2, 1, 1, 0, 0].

Time O(n): each day is pushed once and popped at most once, so there are at most n pops in the entire run, even though they happen inside a while. Space O(n) for the stack, reached when the temperatures only fall.

Why only the top needs checking

Look at the stack column of the walkthrough: the temperatures never increase from bottom to top. That is not a coincidence. A day is pushed only after every cooler day above it has been popped, so each new entry is no warmer than the one beneath it.

That ordering is what makes the loop correct. If today is not warmer than the day on top, it cannot be warmer than anything underneath, because those are at least as warm. So the loop can stop at the first day it fails to resolve, with no need to search further down.

It also explains the efficiency. In row 5, the 72° day resolves two waiting days at once and stops at 75° without looking at anything else.

The same question in other forms

"The next warmer day" is the next greater element problem, and it appears in many disguises: the next taller building, the next higher price, the next larger value in a circular list. Flip the comparison and the same loop finds the next smaller element, which is the heart of Largest Rectangle in Histogram.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

const temperatures = [73, 74, 75, 71, 69, 72, 76, 73];
console.log(dailyTemperatures(temperatures)); // [1, 1, 4, 2, 1, 1, 0, 0]

Python

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temperatures))  # [1, 1, 4, 2, 1, 1, 0, 0]

The comment after each line is the result you should see.

Common mistakes

  • Using if instead of while. One warm day can be the answer for several waiting days, as in rows 5 and 6.
  • Using <= in the comparison. An equal temperature is not warmer. With <=, [50, 50] would give [1, 0] instead of [0, 0].
  • Storing temperatures on the stack. The answer is a distance in days, which needs indexes.
  • Writing the temperature into the result. The entry is day - earlier, the wait, not how warm it became.
  • Adding a final loop to empty the stack. It is unnecessary: the result array already starts filled with zeros.

Original problem: LeetCode 739: Daily Temperatures