Skip to main content
CodePeetCodePeet
CodePeet 150

Daily Temperatures

MEDIUMProblemSolveExternal Links

Description

You are given an array of integers temperatures where temperatures[i] represents the recorded temperature on day i.

For each day, you need to determine: how many days do you have to wait until a warmer temperature occurs?

Return an array answer where answer[i] is the number of days you must wait after day i to encounter a day with a strictly higher temperature. If there is no future day with a warmer temperature, set answer[i] = 0.

In other words, for each position i, find the smallest j > i such that temperatures[j] > temperatures[i], and set answer[i] = j - i. If no such j exists, set answer[i] = 0.

Examples

Example 1

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

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

Explanation:

  • Day 0 (73°): Day 1 is 74° > 73°. Wait 1 day.
  • Day 1 (74°): Day 2 is 75° > 74°. Wait 1 day.
  • Day 2 (75°): Days 3, 4, 5 are all ≤ 75°. Day 6 is 76° > 75°. Wait 4 days.
  • Day 3 (71°): Day 4 is 69° ≤ 71°. Day 5 is 72° > 71°. Wait 2 days.
  • Day 4 (69°): Day 5 is 72° > 69°. Wait 1 day.
  • Day 5 (72°): Day 6 is 76° > 72°. Wait 1 day.
  • Day 6 (76°): No future day is warmer. Answer is 0.
  • Day 7 (73°): No future day exists. Answer is 0.

Example 2

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

Output: [1, 1, 1, 0]

Explanation: Each day except the last has a strictly warmer temperature the very next day. The temperatures are strictly increasing, so every day waits exactly 1 day — except the last day which has no future day.

Example 3

Input: temperatures = [30, 60, 90]

Output: [1, 1, 0]

Explanation: Day 0 waits 1 day for 60°. Day 1 waits 1 day for 90°. Day 2 has no warmer future day.

Constraints

  • 1 ≤ temperatures.length ≤ 10^5
  • 30 ≤ temperatures[i] ≤ 100

Editorial

Brute Force

Intuition

The simplest way to think about this problem is: for each day, look at all the days that come after it and find the first one that is warmer.

Imagine you are checking the weather forecast printed on a calendar. For today's temperature, you flip through the remaining days one by one until you find a day that is warmer. You count how many pages you flipped. Then you go back to tomorrow and repeat the same process.

For each day i, we scan forward through days i+1, i+2, ... until we find a temperature that is strictly greater than temperatures[i]. If we find one at position j, the answer for day i is j - i. If we reach the end without finding a warmer day, the answer is 0.

This requires two nested loops: the outer loop picks each day, and the inner loop scans forward to find the next warmer day.

Step-by-Step Explanation

Let's trace through with temperatures = [73, 74, 75, 71, 69, 72, 76, 73]:

Step 1: Day 0 (73°). Scan forward: Day 1 is 74° > 73°. Found! answer[0] = 1 - 0 = 1.

Step 2: Day 1 (74°). Scan forward: Day 2 is 75° > 74°. Found! answer[1] = 2 - 1 = 1.

Step 3: Day 2 (75°). Scan forward: Day 3 is 71° ≤ 75°. Day 4 is 69° ≤ 75°. Day 5 is 72° ≤ 75°. Day 6 is 76° > 75°. Found! answer[2] = 6 - 2 = 4.

Step 4: Day 3 (71°). Scan forward: Day 4 is 69° ≤ 71°. Day 5 is 72° > 71°. Found! answer[3] = 5 - 3 = 2.

Step 5: Day 4 (69°). Scan forward: Day 5 is 72° > 69°. Found! answer[4] = 5 - 4 = 1.

Step 6: Day 5 (72°). Scan forward: Day 6 is 76° > 72°. Found! answer[5] = 6 - 5 = 1.

Step 7: Day 6 (76°). Scan forward: Day 7 is 73° ≤ 76°. No more days. answer[6] = 0.

Step 8: Day 7 (73°). No future days. answer[7] = 0.

Result: answer = [1, 1, 4, 2, 1, 1, 0, 0]

Brute Force — Scanning Forward from Each Day — Watch how each day scans forward through remaining days to find the next warmer temperature. Notice the repeated work — multiple days end up scanning through the same elements.

Algorithm

  1. Initialize answer array of size n, filled with zeros
  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
        • Break out of the inner loop
  3. Return answer

Code

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> answer(n, 0);
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i;
                    break;
                }
            }
        }
        return answer;
    }
};
class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        answer = [0] * n
        
        for i in range(n):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    answer[i] = j - i
                    break
        
        return answer
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i;
                    break;
                }
            }
        }
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n²)

In the worst case, the inner loop scans nearly the entire remaining array for each element. Consider a strictly decreasing sequence like [100, 99, 98, ..., 1] — every day except the last must scan all the way to the end to determine there is no warmer day. This gives n + (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons, which is O(n²).

Space Complexity: O(1) auxiliary

We only use the answer array which is required as output. No additional data structures are used beyond a few loop variables.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity. With n up to 10^5, the worst case requires approximately 5 × 10^9 comparisons, which would exceed typical time limits of 1-2 seconds.

The fundamental inefficiency is repeated scanning: when we process day 2 (75°) and scan forward past days 3, 4, 5 to reach day 6, we learn that days 3, 4, and 5 are all cooler than 75°. But we discard this information. Later, when we process day 3 (71°), we scan forward past day 4 again — even though we already looked at day 4 during day 2's scan.

Key insight: We can avoid this repeated work by processing temperatures in a way that "remembers" unresolved days. A monotonic stack does exactly this — it keeps track of days that are still waiting for a warmer temperature, ordered so that we can efficiently resolve them when a warmer day finally arrives. Each day is pushed and popped from the stack at most once, giving us O(n) total work.

Bar chart comparing O(n²) brute force vs O(n) monotonic stack for n=100,000
Bar chart comparing O(n²) brute force vs O(n) monotonic stack for n=100,000

Optimal Approach - Monotonic Stack

Intuition

Imagine you are standing in a queue at a theme park, and people are ordered by their temperature. You are looking for someone taller (warmer) than you in front of you. As new people arrive, anyone in the queue who is shorter (cooler) than the newcomer immediately gets their answer — the newcomer is the first taller person they see.

A monotonic decreasing stack implements this idea. We maintain a stack of day indices, where the temperatures form a decreasing sequence from bottom to top. When we encounter a new day with a higher temperature, we pop all days from the stack whose temperatures are lower — because the current day is the answer to their question "when is the next warmer day?"

Here is the process:

  1. Iterate through each day from left to right
  2. While the stack is not empty and the current temperature is greater than the temperature at the stack's top index:
    • Pop the top index from the stack
    • The answer for that popped day is current_index - popped_index
  3. Push the current day's index onto the stack
  4. After processing all days, any indices remaining on the stack have no warmer future day (their answer stays 0)

The stack ensures each element is pushed once and popped at most once, giving O(n) total time. The stack holds indices in decreasing temperature order, which is why it is called a monotonic decreasing stack.

Step-by-Step Explanation

Let's trace through with temperatures = [73, 74, 75, 71, 69, 72, 76, 73]:

Step 1: Day 0 (73°). Stack is empty. Push index 0. Stack: [0].

Step 2: Day 1 (74°). Stack top is index 0 (73°). 74 > 73 → pop index 0. answer[0] = 1 - 0 = 1. Stack is now empty. Push index 1. Stack: [1].

Step 3: Day 2 (75°). Stack top is index 1 (74°). 75 > 74 → pop index 1. answer[1] = 2 - 1 = 1. Stack is now empty. Push index 2. Stack: [2].

Step 4: Day 3 (71°). Stack top is index 2 (75°). 71 ≤ 75 → do not pop. Push index 3. Stack: [2, 3].

Step 5: Day 4 (69°). Stack top is index 3 (71°). 69 ≤ 71 → do not pop. Push index 4. Stack: [2, 3, 4].

Step 6: Day 5 (72°). Stack top is index 4 (69°). 72 > 69 → pop index 4. answer[4] = 5 - 4 = 1. Stack top is now index 3 (71°). 72 > 71 → pop index 3. answer[3] = 5 - 3 = 2. Stack top is index 2 (75°). 72 ≤ 75 → stop popping. Push index 5. Stack: [2, 5].

Step 7: Day 6 (76°). Stack top is index 5 (72°). 76 > 72 → pop index 5. answer[5] = 6 - 5 = 1. Stack top is index 2 (75°). 76 > 75 → pop index 2. answer[2] = 6 - 2 = 4. Stack is empty. Push index 6. Stack: [6].

Step 8: Day 7 (73°). Stack top is index 6 (76°). 73 ≤ 76 → do not pop. Push index 7. Stack: [6, 7].

Step 9: All days processed. Stack contains [6, 7] — these days never found a warmer future day. answer[6] = 0, answer[7] = 0 (default).

Result: answer = [1, 1, 4, 2, 1, 1, 0, 0]

Monotonic Decreasing Stack — Resolving Days When Warmer Temp Arrives — Watch how the stack maintains day indices in decreasing temperature order. When a warmer day arrives, it pops and resolves all cooler days that were waiting.

Algorithm

  1. Initialize answer array of size n, filled with zeros
  2. Initialize an empty stack (will store indices)
  3. For each day i from 0 to n-1:
    • While the stack is not empty AND temperatures[i] > temperatures[stack.top()]:
      • Pop the top index prev from the stack
      • Set answer[prev] = i - prev
    • Push i onto the stack
  4. Return answer (any remaining indices in the stack keep answer = 0)

Code

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> answer(n, 0);
        stack<int> stk;  // stores indices
        
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                int prev = stk.top();
                stk.pop();
                answer[prev] = i - prev;
            }
            stk.push(i);
        }
        return answer;
    }
};
class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = []  # stores indices
        
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                prev = stack.pop()
                answer[prev] = i - prev
            stack.append(i)
        
        return answer
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();  // stores indices
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prev = stack.pop();
                answer[prev] = i - prev;
            }
            stack.push(i);
        }
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n)

Although there is a while loop inside the for loop, the total work is still O(n). Here is why: each index is pushed onto the stack exactly once and popped from the stack at most once. Therefore, across all iterations of the outer loop, the inner while loop executes at most n times in total. The combined work is O(n) pushes + O(n) pops = O(2n) = O(n).

Space Complexity: O(n)

The stack can hold up to n indices in the worst case (when temperatures are strictly decreasing, e.g., [100, 99, 98, ..., 1] — every element gets pushed but nothing gets popped until the end). The answer array is also O(n), but it is required output. So auxiliary space is O(n) for the stack.