Daily Temperature

Question

You are given an array of integers temperatures where temperatures[i] represents the daily temperatures on the ith day.

Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the ith day, set result[i] to 0 instead.

Example 1:

Input: temperatures = [30,38,30,36,35,40,28]

Output: [1,4,1,2,1,0,0]

Example 2:

Input: temperatures = [22,21,20]

Output: [0,0,0]

Constraints:

• 1 <= temperatures.length <= 1000.
• 1 <= temperatures[i] <= 100

Solution

Intuition

The problem in here is how to update the previous items. for example

[30,38,30,36,35,40,28]

Imagine we traverse from left to right, Lets say at 40, how do find and update back the 38 one. As a result, we need a history of the items that we visited and its index, so that we can go back and modify that item.

For storing history, a stack is a good candidate. So it will goes like this:

[30,38,30,36,35,40,28]
  ^
Stack: (index, temperature)
- (0, 30)

Now lets move a pointer, at 38, index 1, we can go back and update the first item (0, 30). Since we know its index, we simply do:

• res[0] = index(38) - index(30) = 1
• now since we finished the item 30 lets pop it out from the list since this is all we need to do with this item based on the question
• Continue to add (1, 38) in

[30,38,30,36,35,40,28]
     ^
Stack: (index, temperature)
- (1, 38)

For 30, we cannot modify anything of the 38, we simply add and continue

[30,38,30,36,35,40,28]
        ^
Stack: (index, temperature)
- (1, 38)
- (2, 30)

For 36, we now can modify the 30, follow the same algorithm, we pop the (2,30) out and modify res[2] = index(36) - 2 = 1

[30,38,30,36,35,40,28]
           ^
Stack: (index, temperature)
- (1, 38)
- (3, 36)

For 35, we cannot adjust both (1, 38) and (3, 36) so we ignore it

[30,38,30,36,35,40,28]
           ^
Stack: (index, temperature)
- (1, 38)
- (3, 36)
- (4, 35)

Now at 40 we can go through each of the item and complete it:

1. (1, 38) -> res[1] = index(40) - index(38) = index(40) - 1 = 5 - 1 = 4
2. (3, 36) -> res[3] = index(40) - index(36) = 5 - 3 = 2
3. (4, 35) -> res[4] = index(40) - index(35) = 5 - 4 = 1

We keep repeating the solution towards the end

Implementation

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []
        
        for i, temp in enumerate(temperatures):
            while stack and stack[-1][1] < temp:
                prevI, prevTemp = stack.pop()
                res[prevI] = i - prevI
            
            stack.append((i, temp))

        return res

Time complexity:

Time $O(n)$
Space: $O(n)$