Leetcode 739. Daily Temperatures

Problem

Leetcode 739 - Daily Temperatures

Example:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Input: temperatures = [30,60,90]
Output: [1,1,0]

Approach

We can iterate through the temperature array and append its (index, temperature)

While stack exists and stack’s last element’s temperature is lower than current day’s temperature, we update the result[stack’s index] = current day - stack’s index. So we know ith day to get warmer

Visualization of the Approach:

temperatures = [73,74,75,71,69,72,76,73]
res = [0,0,0,0,0,0,0,0]
stack = []

stack = [(0,73)]

Since stack[-1][1] < 74, pop stack and update res
res = [1,0,0,0,0,0,0,0]
stack = [(1,74)]

Since stack[-1][1] < 75, pop stack and update res
res = [1,1,0,0,0,0,0,0]
stack = [(2,75)]

res = [1,1,0,0,0,0,0,0]
stack = [(2,75), (3,71)]

res = [1,1,0,0,0,0,0,0]
stack = [(2,75), (3,71), (4, 69)]

Since stack[-1][1] < 72, pop stack and update res
res = [1,1,0,0,1,0,0,0]
stack = [(2,75), (3,71)]

Since stack[-1][1] < 72, pop stack and update res
res = [1,1,0,2,1,0,0,0]
stack = [(2,75)]
stack = [(2,75), (5,72)]

Since stack[-1][1] < 76, pop stack and update res
res = [1,1,0,2,1,1,0,0]
stack = [(2,75)]

Since stack[-1][1] < 76, pop stack and update res
res = [1,1,4,2,1,1,0,0]
stack = []
stack = [(6,76)]

res = [1,1,4,2,1,1,0,0]
stack = [(6,76), (7,73)]

return res = [1,1,4,2,1,1,0,0]

Here is the Python code for the solution:

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = [] 

        for i, t in enumerate(temperatures):
            while stack and stack[-1][1] < t:
                stackI, stackT = stack.pop()
                res[stackI] = i - stackI
            
            stack.append((i,t))
        return res    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$