MediumArrayStackMonotonic Stack

Daily Temperatures

1 approach, code in every language

You are given an array `temperatures` where `temperatures[i]` is the temperature recorded on day `i`.

For each day, determine how many days you must wait until a warmer temperature occurs. If no future day is warmer, the answer for that day is `0`.

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

Example 1

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

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

Day 0 (73) warms up the next day (74), so 1. Day 2 (75) waits 4 days for 76. The last two days never see anything warmer, so 0.

Example 2

Input: temperatures = [30,40,50,60]

Output: [1,1,1,0]

Each day is immediately followed by a warmer one except the final day, which has no warmer future day.

Constraints

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

Decreasing Monotonic Stack of Indices

Hold indices of days still waiting for a warmer temperature; each new day resolves every earlier, cooler day in one pass.

Loading animation…

Intuition

A day only needs to remember the earlier days that have not yet found a warmer temperature. Keep those days' indices on a stack whose temperatures are non-increasing. When the current day is warmer than the day at the top of the stack, that top day has found its warmer day, and the wait is simply the difference in indices. Keep popping while the current day beats the top, resolving each one, then push the current index to wait for its own warmer day. Every index is pushed and popped once, so the whole process is linear.

Algorithm walkthrough

1Create an answer array filled with 0 and an empty stack of indices.
2Iterate i over the days. While the stack is non-empty and temperatures[i] is greater than temperatures at the top index, pop that index j.
3Set answer[j] = i - j, the number of days day j waited.
4Push i onto the stack so it can wait for a warmer future day.
5Any indices remaining on the stack keep their default answer of 0 because no warmer day ever appeared.

Implementation

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = []
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                j = stack.pop()
                answer[j] = i - j
            stack.append(i)
        return answer

Time

O(n)

Space

O(n)

Each day's index enters and leaves the stack at most once, so total work is linear in the number of days.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Nights Until a Fuller House is our own problem on the technique behind Daily Temperatures: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free