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.
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 ; } }Video 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.