Daily Temperatures

Medium

The problem

Given a list of daily temperatures, return a list of the same length where position i tells how many days you must wait after day i to get a warmer day. Put 0 if there is no warmer day in the future.

Example 1
Input: temperatures = [30, 40, 35, 32, 50, 31]
Output: [1, 3, 2, 1, 0, 0]
Day 0 (30) gets warmer the next day (40). Day 1 (40) waits until day 4 (50), so 3 days. Day 2 waits 2 days and day 3 waits 1 day. Days 4 and 5 never see a warmer day.
Example 2
Input: temperatures = [60, 60, 60]
Output: [0, 0, 0]
Equal is not warmer.

Limits

1 ≤ temperatures.length ≤ 100,000
30 ≤ temperatures[i] ≤ 100

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Days are waiting for a warmer day. Which waiting days can you resolve the moment a hot day arrives?

The idea

Keep a stack of indices with decreasing temperatures. For each new day pop every colder day and set its answer to the index gap, then push today.

Target: O(n) time, O(n) space

Go function shape

func dailyTemperatures(temperatures []int) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// DailyTemperatures: days to wait until a warmer day (0 if never).
func DailyTemperatures(temps []int) []int {
	res := make([]int, len(temps))
	stack := []int{}
	for i, t := range temps {
		for len(stack) > 0 && temps[stack[len(stack)-1]] < t {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res[j] = i - j
		}
		stack = append(stack, i)
	}
	return res
}

Read the lesson: Stack Basics