LC739 - Daily Temperatures

Problem

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

Input: temperatures = [73,74,75,71,69,72,76,73]

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

Solution

Use iterate across the temps in the temp list and append the indices to a stack. If the stack has values in it and the temperature pointed to by the index in the end of the stack is less than the current temperature, then the days to wait is the difference between the current index and the index on the stack. Hence, append that value to the results list.

Time complexity is $O(n)$ and we use up to $O(n)$ extra space.

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