Daily Temperatures

MediumstackMonotonic stack (next greater element)stackmonotonic-stackmedium

Maintained by Vikas Dulgunde, software engineer

You are handed a list of daily high temperatures in the order the days occurred. For every position you want to know the distance to the next day that is hotter than the current one.

The answer for a day is the number of positions you have to move forward before you reach a temperature that is strictly greater. A reading that is equal does not count as warmer, so ties are skipped over.

If a day has no warmer day anywhere ahead of it, its answer is 0. Build and return a new list of the same length holding these wait counts.

Examples

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 very next day (74), so 1. Day 2 (75) waits until index 6 (76), a gap of 4. Days 6 and 7 never see anything hotter ahead, so both are 0.

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

Output: [1,1,1,0]

Each day is immediately followed by a hotter one, giving a wait of 1, except the last day which has nothing after it.

Input: temperatures = [90,80,70,60]

Output: [0,0,0,0]

Temperatures only fall, so no day ever has a warmer day ahead and every answer is 0.

Constraints

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100
Only a strictly greater value counts as warmer; equal temperatures are not.

Visible test cases

dailyTemperatures([73,74,75,71,69,72,76,73]) == [1,1,4,2,1,1,0,0]
dailyTemperatures([30,40,50,60]) == [1,1,1,0]
dailyTemperatures([30,60,90]) == [1,1,0]
dailyTemperatures([90,80,70,60]) == [0,0,0,0]
dailyTemperatures([55]) == [0]
dailyTemperatures([70,70,70]) == [0,0,0]

Hints

Hint 1

The brute-force answer for index i is just a forward scan: walk right until you find a bigger value and record the distance. Get that working first.

Hint 2

Notice that once a later, hotter day resolves an earlier waiting day, that earlier day never needs to be looked at again. Can you keep the still-unresolved days somewhere?

Hint 3

Hold the indices of days that are still waiting for a warmer day on a stack, kept in decreasing-temperature order. When today is hotter than the day on top, today resolves it: pop and record the index difference.

Loading the editor...

Approaches

Brute force forward scan

Time O(n^2) · Space O(1) extra beyond the output

For each day, scan every later day until you hit one that is warmer, then store that distance.

Create an answer array of the same length filled with 0.
For each index i, walk j from i+1 to the end.
The moment temperatures[j] is greater than temperatures[i], set answer[i] = j - i and stop scanning.
If the inner scan finishes without a warmer day, answer[i] stays 0.

Monotonic decreasing stack

Time O(n) · Space O(n)

Keep a stack of indices whose warmer day has not been found yet, with their temperatures decreasing from bottom to top. The current day resolves every shallower day it beats in one pass.

Create an answer array filled with 0 and an empty stack of indices.
Iterate i from left to right over the temperatures.
While the stack is not empty and today's temperature is greater than the temperature at the top index, pop that index prev and set answer[prev] = i - prev.
Push the current index i onto the stack.
Indices still on the stack at the end never found a warmer day and keep their 0.

Common mistakes

Treating equal temperatures as warmer. The comparison must be strictly greater, otherwise a flat run like [70,70,70] would report nonzero waits.
Storing temperatures on the stack instead of indices. You need the index to compute the day gap i - prev.
Forgetting that the answer is a count of days to wait, not the warmer temperature itself or its index.
Leaving the default wrong: days that never warm up must end as 0, so initialize the answer array to 0 rather than leaving holes.
Pushing before resolving. Pop all the days the current temperature beats first, then push the current index.

Follow-up variations

Return the warmer temperature value rather than the number of days to wait.
Answer the symmetric question: how many days back was the most recent warmer day (a previous-greater scan).
Support streaming input where temperatures arrive one at a time and you must report each resolved day as soon as it is known.
Generalize to the next element that is at least k degrees warmer instead of strictly warmer by any amount.

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

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 very next day (74), so 1. Day 2 (75) waits until index 6 (76), a gap of 4. Days 6 and 7 never see anything hotter ahead, so both are 0.

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

Output: [1,1,1,0]

Each day is immediately followed by a hotter one, giving a wait of 1, except the last day which has nothing after it.

Input: temperatures = [90,80,70,60]

Output: [0,0,0,0]

Temperatures only fall, so no day ever has a warmer day ahead and every answer is 0.

Hints

Hint 1

The brute-force answer for index i is just a forward scan: walk right until you find a bigger value and record the distance. Get that working first.

Hint 2

Notice that once a later, hotter day resolves an earlier waiting day, that earlier day never needs to be looked at again. Can you keep the still-unresolved days somewhere?

Hint 3

Approaches

Brute force forward scan

Time O(n^2) · Space O(1) extra beyond the output

For each day, scan every later day until you hit one that is warmer, then store that distance.

Create an answer array of the same length filled with 0.
For each index i, walk j from i+1 to the end.
The moment temperatures[j] is greater than temperatures[i], set answer[i] = j - i and stop scanning.
If the inner scan finishes without a warmer day, answer[i] stays 0.

Monotonic decreasing stack

Time O(n) · Space O(n)

Keep a stack of indices whose warmer day has not been found yet, with their temperatures decreasing from bottom to top. The current day resolves every shallower day it beats in one pass.

Create an answer array filled with 0 and an empty stack of indices.
Iterate i from left to right over the temperatures.
While the stack is not empty and today's temperature is greater than the temperature at the top index, pop that index prev and set answer[prev] = i - prev.
Push the current index i onto the stack.
Indices still on the stack at the end never found a warmer day and keep their 0.

Common mistakes

Treating equal temperatures as warmer. The comparison must be strictly greater, otherwise a flat run like [70,70,70] would report nonzero waits.

Storing temperatures on the stack instead of indices. You need the index to compute the day gap i - prev.

Forgetting that the answer is a count of days to wait, not the warmer temperature itself or its index.

Leaving the default wrong: days that never warm up must end as 0, so initialize the answer array to 0 rather than leaving holes.

Pushing before resolving. Pop all the days the current temperature beats first, then push the current index.

Follow-up variations

Return the warmer temperature value rather than the number of days to wait.

Answer the symmetric question: how many days back was the most recent warmer day (a previous-greater scan).

Support streaming input where temperatures arrive one at a time and you must report each resolved day as soon as it is known.

Generalize to the next element that is at least k degrees warmer instead of strictly warmer by any amount.

Daily Temperatures

Examples

Constraints

Hints

Approaches

Brute force forward scan

Monotonic decreasing stack

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Daily Temperatures

Examples

Constraints

Hints

Approaches

Brute force forward scan

Monotonic decreasing stack

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep