Daily Temperatures
MedPrompt
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward nested loop. For each day, it iterates through all subsequent days to find the first day with a warmer temperature.
Algorithm
- Initialize an
answerarray of the same size astemperaturesand fill it with 0s. - Iterate through the
temperaturesarray with indexifrom 0 ton-2. - For each
i, iterate with indexjfromi+1ton-1. - If
temperatures[j]is greater thantemperatures[i], it's the first warmer day. - Set
answer[i] = j - iand break the inner loop. - If the inner loop completes without finding a warmer day,
answer[i]remains 0. - Return the
answerarray.
Walkthrough
The brute-force method is the most intuitive way to solve the problem. We iterate through each day and then, for that day, we search forward in the array to find the first day with a higher temperature.
We use two nested loops. The outer loop, with index i, selects a day. The inner loop, with index j, starts from i+1 and scans the rest of the array. The first time we find temperatures[j] > temperatures[i], we've found our answer for day i. The number of days to wait is simply the difference in their indices, j - i. We store this in our result array at index i and then break the inner loop to proceed to the next day i+1. If the inner loop finishes without finding a warmer day, the result for day i remains 0, which is the default value.
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
Time
O(N^2), where N is the number of temperatures. In the worst-case scenario (a strictly decreasing temperature array), for each element, we have to scan all the remaining elements.
Space
O(N) to store the output array. If the output array is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Doesn't require any complex data structures.
Cons
Highly inefficient for large inputs, likely to result in a 'Time Limit Exceeded' error on coding platforms.
This approach uses a monotonic stack to achieve linear time complexity. The stack stores the indices of days for which we are yet to find a warmer day. By processing the temperatures once, we can efficiently find the next warmer day for multiple previous days.
Algorithm
- Initialize an
answerarray of sizenwith all zeros. - Initialize an empty stack to store indices of the
temperaturesarray. - Iterate through the
temperaturesarray from left to right (indexifrom 0 ton-1). - While the stack is not empty and the temperature of the day at the index on top of the stack is less than the current day's temperature (
temperatures[stack.peek()] < temperatures[i]): - Pop the index
prevIndexfrom the stack. - Calculate the waiting days:
answer[prevIndex] = i - prevIndex. - Push the current index
ionto the stack. - After the loop, any indices left in the stack have no warmer future day, so their answer remains 0.
- Return the
answerarray.
Walkthrough
A more efficient solution involves using a monotonic stack. A monotonic stack is a stack whose elements are always in a sorted order (either increasing or decreasing). For this problem, we use a stack that stores indices of days with monotonically decreasing temperatures.
We iterate through the temperatures from left to right. We maintain a stack of indices of the days we've seen so far. When we are at the current day i, we look at the index at the top of the stack, say prevIndex. If the current temperature temperatures[i] is warmer than temperatures[prevIndex], it means we've found the next warmer day for prevIndex. So, we pop prevIndex from the stack, calculate the wait days as i - prevIndex, and record it. We repeat this process until the stack is empty or the temperature at the top is not less than the current temperature. Finally, we push the current index i onto the stack. This ensures the stack always holds indices of days with decreasing temperatures, waiting for their next warmer day.
import java.util.Stack; class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] answer = new int[n]; Stack<Integer> stack = new Stack<>(); // Stores indices for (int i = 0; i < n; i++) { // While stack is not empty and current temp is warmer than temp at stack's top index while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int prevIndex = stack.pop(); answer[prevIndex] = i - prevIndex; } // Push current index onto the stack stack.push(i); } return answer; }}Complexity
Time
O(N), where N is the number of temperatures. Each index is pushed and popped from the stack at most once, making the total operations proportional to N.
Space
O(N) in the worst case for the stack. For a strictly decreasing array of temperatures, the stack will hold all N indices. This is in addition to the O(N) space for the output array.
Trade-offs
Pros
Optimal time complexity of O(N).
Efficiently solves the problem for large inputs.
Cons
Requires understanding of the stack data structure and the monotonic stack pattern.
Uses extra space for the stack.
Solutions
Solution
class Solution { public int [] dailyTemperatures ( int [] temperatures ) { int n = temperatures . length ; int [] ans = new int [ n ]; Deque < Integer > stk = new ArrayDeque <>(); for ( int i = 0 ; i < n ; ++ i ) { while (! stk . isEmpty () && temperatures [ stk . peek ()] < temperatures [ i ]) { int j = stk . pop (); ans [ j ] = i - j ; } stk . push ( i ); } return ans ; } }/** * @param {number[]} temperatures * @return {number[]} */ var dailyTemperatures = function (temperatures) { const n = temperatures.length; const ans = new Array(n).fill(0); const stk = []; for (let i = n - 1; i >= 0; --i) { while ( stk.length && temperatures[stk[stk.length - 1]] <= temperatures[i] ) { stk.pop(); } if (stk.length) { ans[i] = stk[stk.length - 1] - i; } stk.push(i); } return ans; };class Solution { public: vector < int > dailyTemperatures ( vector < int >& temperatures ) { int n = temperatures . size (); vector < int > ans ( n ); stack < int > stk ; for ( int i = 0 ; i < n ; ++ i ) { while ( ! stk . empty () && temperatures [ stk . top ()] < temperatures [ i ]) { ans [ stk . top ()] = i - stk . top (); stk . pop (); } stk . push ( i ); } return ans ; } };class Solution : def dailyTemperatures ( self , temperatures : List [ int ]) -> List [ int ]: ans = [ 0 ] * len ( temperatures ) stk = [] for i , t in enumerate ( temperatures ): while stk and temperatures [ stk [ - 1 ]] < t : j = stk . pop () ans [ j ] = i - j stk . append ( i ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.