0% completed
Problem Statement
Given an array of integers temperatures
representing daily temperatures, calculate how many days you have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
Examples
Example 1
- Input:
temperatures = [70, 73, 75, 71, 69, 72, 76, 73]
- Output:
[1, 1, 4, 2, 1, 1, 0, 0]
- Explanation: The first day's temperature is 70 and the next day's temperature is 73 which is warmer. So for the first day, you only have to wait for 1 day to get a warmer temperature. Hence, the first element in the result array is 1. The same process is followed for the rest of the days.
Example 2
- Input:
temperatures = [73, 72, 71, 70]
- Output:
[0, 0, 0, 0]
- Explanation: As we can see, the temperature is decreasing every day. So, there is no future day with a warmer temperature. Hence, all the elements in the result array are 0.
Example 3
- Input:
temperatures = [70, 71, 72, 73]
- Output:
[1, 1, 1, 0]
- Explanation: For the first three days, the next day is warmer. But for the last day, there is no future day with a warmer temperature. Hence, the result array is
[1, 1, 1, 0]
.
Constraints:
- 1 <= temperatures.length <= 10<sup>5</sup>
30 <= temperatures[i] <= 100
Solution
To solve the problem efficiently, we use a monotonic decreasing stack. The idea is to go through the temperatures
array from left to right. At each index, we compare the current temperature with the temperatures at the indices stored in the stack. The stack keeps indices of temperatures waiting for a warmer day. If the current temperature is greater than the temperature at the top of the stack, we found a warmer day for that previous index. So, we pop the index from the stack and record the difference in positions (i.e., number of days waited).
We keep doing this while the stack is not empty and the current temperature is warmer than the top element. Once weβve processed all warmer temperatures, we push the current index onto the stack. This process continues until we reach the end of the array. Any index left in the stack does not have a warmer day ahead, so its value remains 0
. The result array is filled accordingly. This approach works in O(n) time using a stack to track pending temperatures.
Step-by-Step Algorithm
-
Initialize data structures:
- Create a
Stack<Integer>
to store indices of unresolved temperatures. - Create an integer array
res
of same length astemperatures
and fill it with 0s.
- Create a
-
Traverse the
temperatures
array:- Loop from
i = 0
totemperatures.length - 1
:
- Loop from
-
For each
temperatures[i]
:- While stack is not empty and
temperatures[i] > temperatures[stack.peek()]
:- Pop the index from the top of the stack β letβs call it
idx
. - This means
temperatures[i]
is the next warmer temperature fortemperatures[idx]
. - Set
res[idx] = i - idx
, because we waitedi - idx
days for a warmer temperature.
- Pop the index from the top of the stack β letβs call it
- While stack is not empty and
-
After checking warmer conditions:
- Push the current index
i
onto the stack (to wait for a warmer temperature in the future).
- Push the current index
-
After the loop ends:
- The
res[]
array contains the final result. - Return
res
.
- The
Algorithm Walkthrough
Initial Setup:
res = [0, 0, 0, 0, 0, 0, 0, 0]
stack = []
Traverse the array:
-
πΉi = 0 β temperature = 70
- Stack is empty β nothing to compare.
- Push index
0
to stack βstack = [0]
res = [0, 0, 0, 0, 0, 0, 0, 0]
-
πΉ i = 1 β temperature = 73
- Stack top β index
0
β temperature at index0
is70
- Compare current temp
73
with temp at index0
β73 > 70
- This means day
1
is warmer than day0
β Pop index0
β Calculate days waited:1 - 0 = 1
β Setres[0] = 1
- Push index
1
to stack βstack = [1]
res = [1, 0, 0, 0, 0, 0, 0, 0]
- Stack top β index
-
πΉ i = 2 β temperature = 75
- Stack top β index
1
β temperature at index1
is73
- Compare current temp
75
with73
β75 > 73
- So, day
2
is warmer than day1
β Pop index1
β Days waited:2 - 1 = 1
β Setres[1] = 1
- Push index
2
βstack = [2]
res = [1, 1, 0, 0, 0, 0, 0, 0]
- Stack top β index
-
πΉ i = 3 β temperature = 71
- Stack top β index
2
β temperature at index2
is75
- Compare
71 < 75
β no warmer temp - Push index
3
βstack = [2, 3]
res = [1, 1, 0, 0, 0, 0, 0, 0]
- Stack top β index
-
πΉ i = 4 β temperature = 69
- Stack top β index
3
β temperature at index3
is71
- Compare
69 < 71
β not warmer - Push index
4
βstack = [2, 3, 4]
res = [1, 1, 0, 0, 0, 0, 0, 0]
- Stack top β index
-
πΉ i = 5 β temperature = 72
-
Stack top β index
4
β temperature =69
β Compare72 > 69
β warmer day found
β Pop index4
β Days waited:5 - 4 = 1
β Setres[4] = 1
-
New stack top β index
3
β temperature =71
β Compare72 > 71
β warmer
β Pop index3
β Days waited:5 - 3 = 2
β Setres[3] = 2
-
New stack top β index
2
β temperature =75
β Compare72 < 75
β not warmer β stop -
Push index
5
βstack = [2, 5]
-
-
res = [1, 1, 0, 2, 1, 0, 0, 0]
-
πΉ i = 6 β temperature = 76
-
Stack top β index
5
β temperature =72
β Compare76 > 72
β warmer
β Pop index5
β Days waited:6 - 5 = 1
β Setres[5] = 1
-
New stack top β index
2
β temperature =75
β Compare76 > 75
β warmer
β Pop index2
β Days waited:6 - 2 = 4
β Setres[2] = 4
-
Stack now empty
-
Push index
6
βstack = [6]
-
res = [1, 1, 4, 2, 1, 1, 0, 0]
-
-
πΉ i = 7 β temperature = 73
- Stack top β index
6
β temperature =76
β Compare73 < 76
β not warmer - Push index
7
βstack = [6, 7]
res = [1, 1, 4, 2, 1, 1, 0, 0]
- Stack top β index
Final Stack:
stack = [6, 7]
- No warmer days found for index 6 and 7 β leave
res[6]
andres[7]
as 0
Final Output:
res = [1, 1, 4, 2, 1, 1, 0, 0]
Code
Here is how we can implement this algorithm:
Complexity Analysis
Time Complexity: O(n)
Where n is the number of elements in the temperatures
array.
- Every index
i
is pushed exactly once onto the stack. - Every index is popped at most once.
- The
while
loop might look nested, but the total number of stack operations across the whole loop is O(n) β each element is pushed and popped once.
So, we do O(n) work even though thereβs a loop inside a loop. Itβs efficient due to the monotonic stack.
Space Complexity: O(n)
- The stack can hold up to n elements in the worst case (if the temperatures keep going down).
- The result array
res[]
also uses O(n) space.
So total space is O(n) due to:
- the stack, and
- the output array.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible