Daily Temperatures

LeetCode 739: Daily Temperatures Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a monotonic stack to store indices of days with temperatures that haven't yet seen a warmer day, processing the array in a single pass to achieve linear time complexity.

The Daily Temperatures problem asks us to process an array of integers representing daily weather. For each day, we must calculate the number of days one must wait until a warmer temperature occurs. If no future day is warmer, the answer for that day is 0. This is a classic "Next Greater Element" problem, making LeetCode 739 a popular interview question for testing data structure proficiency.

Brute Force Approach for Daily Temperatures

The most intuitive way to solve this problem is to check every future day for each specific day until a warmer temperature is found.

For a specific day i, we iterate through all subsequent days j (where j > i). The first time we encounter temperatures[j] > temperatures[i], the difference j - i is the answer. If we reach the end of the array without finding a warmer day, the answer is 0.

1# Pseudo-code for Brute Force
2for i from 0 to length - 1:
3    found = false
4    for j from i + 1 to length - 1:
5        if temperatures[j] > temperatures[i]:
6            answer[i] = j - i
7            found = true
8            break
9    if not found:
10        answer[i] = 0

Complexity Analysis: The time complexity of this approach is O(N^2). In the worst-case scenario (e.g., a sorted decreasing array like [99, 98, 97, ...]), for every element i, we scan all remaining N-1-i elements. With constraints allowing N up to 100,000, an O(N^2) solution performs approximately 10 billion operations, which results in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Stack Patterns

1. Initialization: Create an array answer of the same length as the input, initialized to 0. Create an empty stack to store indices (integers).
2. Iteration: Traverse the temperatures array from left to right (index i from 0 to N-1).
3. Monotonic Maintenance (The While Loop):
   • Check if the stack is not empty.
   • Compare the current temperature (temperatures[i]) with the temperature at the index stored at the top of the stack (temperatures[stack.peek()]).
   • If temperatures[i] is greater, it means the current day is the warmer day for the index at the top of the stack.
4. Resolution:
   • Pop the index (prev_index) from the stack.
   • Calculate the wait days: i - prev_index.
   • Store this value in answer[prev_index].
   • Repeat the check until the stack is empty or the condition fails.
5. Push: Push the current index i onto the stack.
6. Completion: Any indices remaining in the stack after the loop finishes naturally have 0 as their answer (default initialization), representing that no warmer day exists.

Execution Flow

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

1. i = 0 (73): Stack is empty. Push 0. Stack: [0].
2. i = 1 (74): 74 > temperatures[0] (73).
   • Pop 0. answer[0] = 1 - 0 = 1.
   • Stack empty. Push 1. Stack: [1].
3. i = 2 (75): 75 > temperatures[1] (74).
   • Pop 1. answer[1] = 2 - 1 = 1.
   • Stack empty. Push 2. Stack: [2].
4. i = 3 (71): 71 < 75. Push 3. Stack: [2, 3]. (Note: temps are decreasing 75 -> 71).
5. i = 4 (69): 69 < 71. Push 4. Stack: [2, 3, 4]. (Temps: 75 -> 71 -> 69).
6. i = 5 (72): 72 > temperatures[4] (69).
   • Pop 4. answer[4] = 5 - 4 = 1. Stack: [2, 3].
   • Check Top: 72 > temperatures[3] (71).
   • Pop 3. answer[3] = 5 - 3 = 2. Stack: [2].
   • Check Top: 72 < temperatures[2] (75). Stop popping.
   • Push 5. Stack: [2, 5].
7. i = 6 (76): 76 > temperatures[5] (72).
   • Pop 5. answer[5] = 6 - 5 = 1.
   • 76 > temperatures[2] (75).
   • Pop 2. answer[2] = 6 - 2 = 4.
   • Push 6. Stack: [6].
8. i = 7 (73): 73 < 76. Push 7. Stack: [6, 7].
9. End: Remaining indices 6 and 7 have answer 0.

Proof of Correctness

The algorithm is correct because it strictly adheres to the definition of the problem. We only pop an index prev_index when we find a current index i such that temperatures[i] > temperatures[prev_index]. Since we iterate from left to right, the first time this condition is met for prev_index, i is guaranteed to be the nearest future day with a warmer temperature. The Stack invariant (strictly decreasing temperatures) ensures that any index remaining in the stack has not yet encountered a warmer temperature.

Pattern Reuse Notes

The Monotonic Stack pattern used here is directly applicable to several other high-frequency interview problems. Mastery of this pattern allows you to solve:

• LeetCode 402: Remove K Digits - Uses a monotonic stack to find the smallest subsequence.
• LeetCode 496: Next Greater Element I - A simplified version of Daily Temperatures using a map and stack.
• LeetCode 503: Next Greater Element II - Applies the same logic on a circular array.
• LeetCode 901: Online Stock Span - Calculates spans using a monotonic stack in an online (streaming) setting.

Reference Implementation

C++ Solution for LeetCode 739

1#include <vector>
2#include <stack>
3
4class Solution {
5public:
6    std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
7        int n = temperatures.size();
8        std::vector<int> answer(n, 0);
9        std::stack<int> st; // Stores indices
10
11        for (int i = 0; i < n; ++i) {
12            // While stack is not empty and current temp is warmer than
13            // the temp at the index stored at the top of the stack
14            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
15                int prevIndex = st.top();
16                st.pop();
17                answer[prevIndex] = i - prevIndex;
18            }
19            st.push(i);
20        }
21
22        return answer;
23    }
24};

Java Solution for LeetCode 739

1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class Solution {
5    public int[] dailyTemperatures(int[] temperatures) {
6        int n = temperatures.length;
7        int[] answer = new int[n];
8        // Using ArrayDeque is generally faster than Stack in Java
9        Deque<Integer> stack = new ArrayDeque<>();
10
11        for (int i = 0; i < n; i++) {
12            // Check if current temp is warmer than the temp at the top index
13            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
14                int prevIndex = stack.pop();
15                answer[prevIndex] = i - prevIndex;
16            }
17            stack.push(i);
18        }
19
20        return answer;
21    }
22}

Python Solution for LeetCode 739

1from typing import List
2
3class Solution:
4    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
5        n = len(temperatures)
6        answer = [0] * n
7        stack = [] # Stores indices
8
9        for i, current_temp in enumerate(temperatures):
10            # While stack is not empty and current temp is warmer
11            while stack and current_temp > temperatures[stack[-1]]:
12                prev_index = stack.pop()
13                answer[prev_index] = i - prev_index
14            
15            stack.append(i)
16            
17        return answer