Daily Temperatures
Problem
Given a list of daily temperatures, return a list such that for each day, it tells how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
- 1 ≤ temperatures.length ≤ 10⁵
- 30 ≤ temperatures[i] ≤ 100
Example
temperatures = [73,74,75,71,69,72,76,73][1,1,4,2,1,1,0,0]Starting at day 0 with temperature 73, the next warmer day is day 1 with 74, so answer[0] = 1. For day 1 (74), the next warmer day is day 2 (75), so answer[1] = 1. For day 2 (75), the next warmer day is day 6 (76), which is 4 days later, so answer[2] = 4. For day 3 (71), the next warmer day is day 5 (72), so answer[3] = 2. For day 4 (69), the next warmer day is day 5 (72), so answer[4] = 1. For day 5 (72), the next warmer day is day 6 (76), so answer[5] = 1. Days 6 and 7 have no warmer future days, so their answers are 0.
Approach
Straightforward Solution
A brute-force approach checks for each day all future days until a warmer temperature is found, resulting in O(n^2) time complexity, which is too slow for large inputs.
Core Observation
For each day, the answer depends on finding the next day with a strictly higher temperature. This is a classic 'next greater element' problem where the relative order of days matters and we want to efficiently find the next warmer day for each index.
Path to Optimal
The key recognition signals are 'next warmer day', 'for each element find next greater element', and 'efficient lookup'. These indicate the Monotonic Stack pattern because it maintains a stack of indices with temperatures in decreasing order, allowing the algorithm to find the next greater element in O(n) time by popping smaller elements when a warmer temperature is found.
Optimal Approach
Use a monotonic decreasing stack to store pairs of (temperature, index). Iterate through the temperatures array. For each temperature, pop from the stack while the current temperature is greater than the temperature at the top of the stack. For each popped element, calculate the difference in indices to find how many days to wait. Push the current temperature and index onto the stack. This ensures each element is pushed and popped at most once, resulting in O(n) time complexity.
Time
O(n)
Each temperature is pushed onto the stack once and popped at most once, resulting in linear time complexity.
Space
O(n)
The stack can hold up to all elements in the worst case (strictly decreasing temperatures), and the output array is also O(n), which is required by the problem.
Pattern Spotlight
Monotonic Stack (Next Greater Element)
Maintain a stack of indices whose corresponding values form a strictly decreasing sequence; when a new value breaks this order, pop all smaller elements to resolve their 'next greater' answers immediately, ensuring each element is processed once.
Solution
| 1 | class Solution:
|
| 2 | def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
|
| 3 | res = [0] * len(temperatures)
|
| 4 | stack = []
|
| 5 |
|
| 6 | for i, t in enumerate(temperatures):
|
| 7 | while stack and t > stack[-1][0]:
|
| 8 | stack_temp, stack_i = stack.pop()
|
| 9 | res[stack_i] = i - stack_i
|
| 10 | stack.append([t, i])
|
| 11 |
|
| 12 | return res |
| 1 | import java.util.ArrayDeque; |
| 2 | import java.util.Deque; |
| 3 | |
| 4 | class Solution { |
| 5 | public int[] dailyTemperatures(int[] temperatures) { |
| 6 | int[] res = new int[temperatures.length]; |
| 7 | Deque<int[]> stack = new ArrayDeque<>(); |
| 8 | |
| 9 | for (int i = 0; i < temperatures.length; i++) { |
| 10 | int t = temperatures[i]; |
| 11 | while (!stack.isEmpty() && t > stack.peek()[0]) { |
| 12 | int[] stackTop = stack.pop(); |
| 13 | res[stackTop[1]] = i - stackTop[1]; |
| 14 | } |
| 15 | stack.push(new int[] {t, i}); |
| 16 | } |
| 17 | |
| 18 | return res; |
| 19 | } |
| 20 | } |
| 1 | #include <vector> |
| 2 | #include <stack> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | vector<int> dailyTemperatures(vector<int>& temperatures) { |
| 9 | vector<int> res(temperatures.size(), 0); |
| 10 | stack<pair<int, int>> stk; // pair<temperature, index> |
| 11 | |
| 12 | for (int i = 0; i < (int)temperatures.size(); ++i) { |
| 13 | int t = temperatures[i]; |
| 14 | while (!stk.empty() && t > stk.top().first) { |
| 15 | auto [stack_temp, stack_i] = stk.top(); |
| 16 | stk.pop(); |
| 17 | res[stack_i] = i - stack_i; |
| 18 | } |
| 19 | stk.emplace(t, i); |
| 20 | } |
| 21 | |
| 22 | return res; |
| 23 | } |
| 24 | }; |
| 1 | var dailyTemperatures = function(temperatures) { |
| 2 | const res = new Array(temperatures.length).fill(0); |
| 3 | const stack = []; |
| 4 | |
| 5 | for (let i = 0; i < temperatures.length; i++) { |
| 6 | const t = temperatures[i]; |
| 7 | while (stack.length > 0 && t > stack[stack.length - 1][0]) { |
| 8 | const [stackTemp, stackI] = stack.pop(); |
| 9 | res[stackI] = i - stackI; |
| 10 | } |
| 11 | stack.push([t, i]); |
| 12 | } |
| 13 | |
| 14 | return res; |
| 15 | }; |
Step-by-Step Solution
Initialize Result Array and Monotonic Stack
| 3 | res = [0] * len(temperatures)
|
| 4 | stack = []
|
Objective
To prepare the output array with default values and create a stack to track unresolved temperatures.
Key Insight
Initializing the result array with zeros handles the default case where no warmer day exists. The stack will hold pairs of (temperature, index) in decreasing order, enabling efficient resolution of next warmer days as the iteration progresses.
Interview Quick-Check
Core Logic
The result array is pre-filled with zeros to represent days with no warmer future temperature by default.
State & Boundaries
The stack starts empty and will only contain indices of days for which the next warmer day is not yet found.
Iterate Through Temperatures and Resolve Next Warmer Days
| 6 | for i, t in enumerate(temperatures):
|
| 7 | while stack and t > stack[-1][0]:
|
| 8 | stack_temp, stack_i = stack.pop()
|
| 9 | res[stack_i] = i - stack_i
|
| 10 | stack.append([t, i])
|
Objective
To process each day's temperature, updating the result for previous days that find their next warmer day.
Key Insight
By iterating through the temperatures, the algorithm compares the current temperature with the top of the stack. If the current temperature is warmer, it resolves all previous days with lower temperatures by popping them and calculating the waiting days. This approach leverages the monotonic property to efficiently find next greater elements without redundant comparisons.
Interview Quick-Check
Core Logic
The while loop pops all stack elements with temperatures less than the current temperature, resolving their next warmer day in one pass.
State & Boundaries
The iteration uses enumerate to track both index and temperature, which are essential for calculating the waiting days.
Common Pitfalls & Bugs
Failing to update the result array inside the while loop or incorrectly calculating the index difference leads to wrong answers.
Complexity
Each element is pushed and popped at most once, ensuring O(n) time complexity.
Return the Computed Result Array
| 12 | return res |
Objective
To output the final array containing the number of days to wait for a warmer temperature for each day.
Key Insight
After processing all temperatures, the result array contains the correct waiting times for all days. Days without a warmer future day remain zero, as initialized.
Interview Quick-Check
Core Logic
Returning the precomputed result array completes the solution.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
while stack and t > stack[-1][0]:While the stack is not empty and current temperature is warmer than the top of the stack's temperature, pop from stack.
This loop resolves all previous days with temperatures lower than the current one, ensuring that each popped day finds its next warmer day immediately, which is the core of the monotonic stack approach.
res[stack_i] = i - stack_iCalculate and store the number of days waited for a warmer temperature for the popped day.
The difference between the current index and the popped index gives the exact number of days waited, which is the required output for that day.
stack = []Create an empty stack to store pairs of (temperature, index).
The stack maintains a strictly decreasing sequence of temperatures, enabling efficient identification of the next warmer day by popping smaller temperatures when a warmer one is found.
stack.append([t, i])Push the current temperature and index onto the stack.
Adding the current day to the stack maintains the decreasing temperature order, ensuring future warmer days can resolve it correctly.
res = [0] * len(temperatures)Initialize the result array with zeros for all days.
Pre-filling the result array with zeros handles the default case where no warmer future day exists, avoiding extra checks later.
stack_temp, stack_i = stack.pop()Pop the top element from the stack, retrieving its temperature and index.
Popping the stack removes the day whose next warmer day has been found, allowing the algorithm to update its result and continue processing remaining unresolved days.
return resReturn the completed result array.
After processing all days, the result array contains the correct waiting times for each day, fulfilling the problem's requirements.
for i, t in enumerate(temperatures):Iterate over each temperature with its index.
Enumerate provides both the day index and temperature, which are necessary for calculating the waiting days and managing the stack.
Test Your Understanding
Why does using a monotonic stack guarantee that each element is processed only once, ensuring O(n) time?
Because each element is pushed onto the stack exactly once and popped at most once when a warmer temperature is found, the total number of stack operations is linear in the number of elements.
Related Problems
Stacks pattern
Don't just read it. Drill it.
Reconstruct Daily Temperatures from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Daily Temperatures drill