AlgoMaster Logo

Daily Temperatures

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We have a list of daily temperatures and, for each day, we need to figure out how many days until a strictly warmer temperature occurs. If no warmer day exists in the future, the answer for that day is 0.

A direct scan works: for each day, look forward until something warmer appears. But many days can share the same next warmer day. When temperatures fall for several days and then spike, that one spike is the answer for every day in the falling stretch. An algorithm that resolves all of those days at once, the moment the spike arrives, avoids the repeated scanning. A stack of unresolved days supports this: accumulate days as they pass, then pop everything cooler when a warmer day shows up.

Key Constraints:

  • 1 <= temperatures.length <= 10^5: with up to 100,000 elements, an O(n^2) brute force can reach 10^10 operations in the worst case. We need O(n) or O(n log n).
  • 30 <= temperatures[i] <= 100: temperatures span only 71 distinct values. The space-optimized approach later in this chapter relies on this narrow range for its runtime bound.

Approach 1: Brute Force

Intuition

Do what the problem describes: for each day, look at every future day until one is warmer, and record the distance. If the scan reaches the end without finding one, the answer stays 0.

This is correct but does a lot of repeated scanning. If temperatures decrease for a long stretch and then spike, every day in that stretch scans all the way to the spike independently.

Algorithm

  1. Create a result array of the same length, initialized to 0.
  2. For each day i from 0 to n-1:
    • For each future day j from i+1 to n-1:
      • If temperatures[j] > temperatures[i], set answer[i] = j - i and break.
  3. Return the result array.

Example Walkthrough

1i=0 (73): scan forward, j=1 (74) > 73 → answer[0] = 1
0
i
73
1
74
j
2
75
3
71
4
69
5
72
6
76
7
73
1/7

Code

With n up to 10^5, the O(n^2) worst case is too slow. The waste is the repeated scanning: many days scan to the same warmer day independently. The next approach accumulates unresolved days and resolves them in batches the moment a warmer day appears.

Approach 2: Monotonic Stack

Intuition

Instead of having each day search forward for its answer, flip the perspective: process days left to right and maintain a stack of days that have not yet found a warmer future day. The stack holds indices, and the temperatures at those indices are in non-increasing order from bottom to top (a monotonic decreasing stack, where equal temperatures sit together).

When a new day arrives, compare it against the index on top of the stack. If today is warmer, today is the answer for that stacked day: pop it and record the distance. Keep popping as long as today is warmer than the stack's top, because today resolves all of those cooler days. Then push today onto the stack.

Algorithm

  1. Create a result array of size n, initialized to 0.
  2. Create an empty stack that will hold indices.
  3. Iterate through each day i from 0 to n-1:
    • While the stack is not empty and temperatures[i] > temperatures[stack.top]:
      • Pop the top index prevDay from the stack.
      • Set answer[prevDay] = i - prevDay.
    • Push i onto the stack.
  4. Any indices remaining on the stack never found a warmer day, so their answers stay 0.
  5. Return the result array.

Example Walkthrough

1Day 0 (73): stack empty, push index 0
0
73
i=0
1
74
2
75
3
71
4
69
5
72
6
76
7
73
1/7

Code

The monotonic stack is O(n) in time, which is optimal, but it uses O(n) extra space for the stack. The final approach removes the stack by processing days from right to left and using the answer array itself to skip ahead.

Approach 3: Optimized Space - Right-to-Left with Answer Array

Intuition

Processing days from right to left means the answers for all future days are already computed, and each one can serve as a jump pointer.

For day i, check day i+1. If it is warmer, the answer is 1. If not, answer[i+1] gives the distance to the next warmer day after i+1, so jump to i + 1 + answer[i+1] and check that day instead. Keep jumping until a warmer day appears, or until a day with answer = 0 is reached, which means no warmer day exists from that point forward.

This removes the stack entirely. The answer array doubles as the navigation structure.

Algorithm

  1. Create a result array of size n, initialized to 0.
  2. Iterate from day n-2 down to 0 (the last day's answer is always 0):
    • Set j = i + 1.
    • While temperatures[j] <= temperatures[i]:
      • If answer[j] == 0, no warmer day exists from j onward, so answer[i] = 0. Break.
      • Otherwise, jump forward: j = j + answer[j].
    • If we exited because temperatures[j] > temperatures[i], set answer[i] = j - i.
  3. Return the result array.

Example Walkthrough

1Start from right. Day 7: last day, answer=0. Day 6 (76): day 7 (73) ≤ 76, no warmer
0
73
1
74
2
75
3
71
4
69
5
72
6
i=6
76
7
73
j=7
1/7

Code