Loading problems...
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.
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.
# Pseudo-code for Brute Force
for i from 0 to length - 1:
found = false
for j from i + 1 to length - 1:
if temperatures[j] > temperatures[i]:
answer[i] = j - i
found = true
break
if not found:
answer[i] = 0Complexity 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.
The inefficiency of the brute force approach stems from redundant comparisons. We repeatedly scan the same future elements for different past days.
The core insight of the Monotonic Stack pattern here is to process the array linearly while maintaining a "pending" list of days. Instead of looking forward from the current day, we look backward at previous days that haven't found a warmer day yet.
We maintain a stack of indices. The invariant we enforce is that the temperatures corresponding to the indices in the stack are in strictly decreasing order.
Why decreasing?
Visual Description: Imagine iterating through the array. The stack acts as a container for indices of days with "unresolved" temperatures.

Let's trace temperatures = [73, 74, 75, 71, 69, 72, 76, 73].
0. Stack: [0].74 > temperatures[0] (73).
0. answer[0] = 1 - 0 = 1.1. Stack: [1].75 > temperatures[1] (74).
1. answer[1] = 2 - 1 = 1.2. Stack: [2].71 < 75. Push 3. Stack: [2, 3]. (Note: temps are decreasing 75 -> 71).69 < 71. Push 4. Stack: [2, 3, 4]. (Temps: 75 -> 71 -> 69).72 > temperatures[4] (69).
4. answer[4] = 5 - 4 = 1. Stack: [2, 3].72 > temperatures[3] (71).3. answer[3] = 5 - 3 = 2. Stack: [2].72 < temperatures[2] (75). Stop popping.5. Stack: [2, 5].76 > temperatures[5] (72).
5. answer[5] = 6 - 5 = 1.76 > temperatures[2] (75).2. answer[2] = 6 - 2 = 4.6. Stack: [6].73 < 76. Push 7. Stack: [6, 7].6 and 7 have answer 0.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.
cpp#include <vector> #include <stack> class Solution { public: std::vector<int> dailyTemperatures(std::vector<int>& temperatures) { int n = temperatures.size(); std::vector<int> answer(n, 0); std::stack<int> st; // Stores indices for (int i = 0; i < n; ++i) { // While stack is not empty and current temp is warmer than // the temp at the index stored at the top of the stack while (!st.empty() && temperatures[i] > temperatures[st.top()]) { int prevIndex = st.top(); st.pop(); answer[prevIndex] = i - prevIndex; } st.push(i); } return answer; } };
javaimport java.util.ArrayDeque; import java.util.Deque; class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] answer = new int[n]; // Using ArrayDeque is generally faster than Stack in Java Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // Check if current temp is warmer than the temp at the top index while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int prevIndex = stack.pop(); answer[prevIndex] = i - prevIndex; } stack.push(i); } return answer; } }
pythonfrom typing import List class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: n = len(temperatures) answer = [0] * n stack = [] # Stores indices for i, current_temp in enumerate(temperatures): # While stack is not empty and current temp is warmer while stack and current_temp > temperatures[stack[-1]]: prev_index = stack.pop() answer[prev_index] = i - prev_index stack.append(i) return answer
while loop, each element (index) is pushed onto the stack exactly once and popped at most once. The total number of stack operations is proportional to N.N indices.The Monotonic Stack pattern used here is directly applicable to several other high-frequency interview problems. Mastery of this pattern allows you to solve:
Why does my solution get Time Limit Exceeded (TLE)?
Why is my answer calculating the wrong difference?
current_index - prev_index without the stored index.Why are some days showing incorrect 0s or negative numbers?
>= instead of >).