LC 739 - Daily Temperatures

Question

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]

Example 3:

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

Constraints:

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

Links

Question here and solution here

Solution

concept

We can write a $O(n^2)$ solution quite easily with 2 for loop. The main technique for an $O(n)$ is a monotonic stack, specifically a monotonically decreasing stack.

Since we are looking for the next higher temperature, our stack will keep appending values (in this case we add in a list since we need to keep track of the index, i.e. [temperature, idx]) if the new value is less than the top of the stack (i.e. cur_val < stack[-1]), once we have encountered a higher temperature, we keep popping the top of the stack until cur_val == stack[-1], each time we pop we calculate the difference between the popped index and the current value’s index (that is the number of days that this popped temperature will have to wait for the higher temperature.) The trick here is we update the answer array at specific index of temperature we popped.

We can also iterate the list from reverse and update all values one by one from the back.

code

class Solution:
	"""
	neetcode solution
	iterate normally but only insert answer at the right index
	more intuitive
	"""
	def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
		stack = [] # [temperature, idx]
		ans = [0] * len(temperatures)

		for idx, temp in enumerate(temperatures):
			while stack and stack[-1][0] < temp:
				temperature, index = stack.pop()
				ans[index] = idx - index

			stack.append([temp, idx])

		return ans

class Solution:
	"""
	monotonically decreasing stack
	iterate from reverse and add the answer in sequence from the back
	"""
	def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
		stack = [] # [temp, idx]
		ans = [0] * len(temperatures)

		for i in range(len(temperatures)-1, -1, -1):
			while stack and stack[-1][0] <= temperatures[i]:
				stack.pop()

			if not stack:
				ans[i] = 0
			else:
				ans[i] = stack[-1][1] - i

			stack.append([temperatures[i], i])

		return ans

Complexity

time: $O(n)$.
space: $O(n)$