Problem Description

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]

My Idea

The idea here is to construct a stack of monotonically decreasing values. Every time we see a value that is greater than the topmost value in the stack we start popping from it until the current value is the lowest one in the stack. For each pop(), we add the difference between the indices of the popped element and the current one at the position of the popped element in the anwer array. This results in a time and space complexity of O(n)

My solution

# Time Complexity: O(n)
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    answer = [0]*len(temperatures)
    stack = []
    for i, t in enumerate(temperatures):
        while stack and t > stack[-1][0]:
            st, si = stack.pop()
            answer[si] = i-si
        stack.append([t,i])
    return answer