AlgoMaster Logo

Daily Temperatures

Last Updated: April 1, 2026

medium
4 min read

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.

The brute force instinct is obvious: for each day, scan forward until you find something warmer. But notice that many days might share the same "next warmer day." For instance, if temperatures drop for several days and then spike, that spike resolves multiple days at once. This batching behavior is the key insight, and it points directly at a stack-based approach where we accumulate unresolved days and pop them off when a warmer day arrives.

Key Constraints:

  • 1 <= temperatures.length <= 10^5 -- With up to 100,000 elements, an O(n^2) brute force would hit 10^10 operations in the worst case. We need O(n) or O(n log n).
  • 30 <= temperatures[i] <= 100 -- Temperatures live in a narrow range of only 71 distinct values. This opens the door to counting-based optimizations, though O(n) stack approaches are simpler.

Approach 1: Brute Force

Intuition

The simplest approach is exactly what the problem describes: for each day, look at every future day until you find one that is warmer. If you find it, record the distance. If you reach the end without finding one, the answer is 0.

This works correctly but does a lot of repeated scanning. If the temperatures are decreasing for a long stretch followed by a 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

This approach works but is too slow for the constraint of n up to 10^5. Many days end up scanning to the same warmer day independently. What if we accumulated unresolved days and resolved them all at once when 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 decreasing order (a monotonic decreasing stack).

When we arrive at a new day, we check: is today's temperature warmer than the temperature at the index on top of the stack? If so, today is the answer for that stacked day. We pop it off and record the distance. We keep popping as long as today is warmer than the stack's top, because today resolves all of those cooler days. Then we push today onto the stack.

The beauty of this approach is that each index is pushed once and popped once, so the total work across all days is O(n), even though the inner while loop might pop multiple elements on some iterations.

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 already O(n) in time, which is optimal. But it uses O(n) extra space for the stack. What if we processed from right to left and used the answer array itself to skip ahead, eliminating the stack entirely?

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

Intuition

Here is a clever observation: if we process days from right to left, and we have already computed the answer for future days, we can use those answers as "jump pointers" to skip ahead.

For day i, we check day i+1. If it is warmer, great, the answer is 1. If not, we know that answer[i+1] tells us the next warmer day after i+1. So we jump to i + 1 + answer[i+1] and check that day. We keep jumping until we either find a warmer day or land on a day with answer = 0 (meaning no warmer day exists from that point forward).

This eliminates the need for a stack entirely. We use the answer array itself as our 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