Daily Temperatures

The key idea

Keep a stack of day indices whose answer is still unknown, with their temperatures decreasing from bottom to top. When a warmer day arrives it resolves every colder day sitting on top of the stack at once, and the gap is just the difference of the two indices.

Problem

You are given an array temperatures where temperatures[i] is the temperature on the i-th day. For each day, return how many days you have to wait until a warmer temperature. If there is no future day with a warmer temperature, put 0 for that day.

Return an array answer such that answer[i] is the number of days you wait after day i to get a warmer temperature.

Constraints

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

Examples

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]

Complexity

Time: O(n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →