Daily Temperatures

The Problem

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 <= 10^5
• 30 <= temperatures[i] <= 100

The Monotonic Bouncer Line Analogy

Imagine each future day lining up outside a club, and today's day is asking the bouncer one question: "Who is the first guest ahead of me who is strictly hotter than I am?"

The bouncer does not keep every future guest in line. That would make the line noisy and useless. Instead, the bouncer keeps only the guests who are still worth asking about. If a new guest arrives who is hotter than or equal to someone already standing closer to the front, that cooler guest gets turned away immediately. Any earlier day would always prefer the newer, hotter guest, so the cooler one has become dead weight.

That leaves a very disciplined line of future candidates. The guest at the front is always the nearest future day that still has a chance to help someone further left. If today's temperature is cooler than that front guest, the answer is immediate: count how many days away that guest is. If today's temperature is hotter or equal, the bouncer keeps kicking guests out until the front is finally hotter or the line goes empty.

Understanding the Analogy

The Setup

We are not asking whether some warmer day exists somewhere in the future. We are asking for the first warmer future day. That "first" requirement is what makes order matter.

So the line cannot just remember the hottest future day. It must remember future days in a way that still preserves the nearest valid answer for every earlier day we will inspect.

Why Cooler Guests Get Turned Away

Suppose a future day with temperature 71 is already waiting in line, and then a nearer future day with temperature 72 arrives in front of it. The 71 day is now useless for every earlier day. Any earlier day that would have accepted 71 would also accept 72, and 72 is closer.

Equal temperatures are useless too. If the current day is 70, another future 70 is not warm enough to answer the question. And if a later 70 sits behind a nearer 70, the farther one can never be the first warmer answer for anyone.

That is why the bouncer removes future days whose temperature is less than or equal to the current day's temperature. They can no longer help anyone to the left.

Why This Approach

If each day scanned every future day until it found a warmer one, the work could blow up to O(n^2). The bouncer line avoids repeated scanning because each day enters the line once and can be kicked out at most once.

That gives us a monotonic stack of day indices and an O(n) solution. The stack stores the future days still worth asking about, and its top is always the nearest remaining candidate.

How I Think Through This

I scan temperatures from right to left because the answer for day i depends only on days after i. I keep a stack named futureLine that stores indices, not temperatures. The invariant is: after cleanup, the top of futureLine is the nearest future day that is strictly warmer than the current day.

For each day, I first compare its temperature to the temperature at the top index in futureLine. While that future day is cooler than or equal to today, I pop it because it cannot help this day or any earlier day anymore. After that cleanup, if futureLine is non-empty, the top index is the first warmer future day, so waitDays[day] = futureLine[futureLine.length - 1] - day. If the stack is empty, no warmer day exists, so the default 0 stays in place. Then I push day onto futureLine so earlier days can ask about it.

Take [73,74,75,71,69,72,76,73].

Building the Algorithm

Step 1: Start the Answer Sheet

Before the bouncer line can help, the function needs a place to write answers. Start by creating waitDays with one slot per day, all preset to 0.

That default is not filler. It already matches the real meaning of "no warmer future day exists." So the first step is not algorithm scaffolding hidden by the author. It is the first structural line the learner genuinely owns.

Hints & gotchas

• Own the first line: do not skip straight to stacks and loops before the answer array exists.
• One slot per day: the returned array must match the input length exactly.
• Zeros already mean something: they are not placeholders; they are the correct result when no warmer day is found.

Step 2: Build the Future Line Shell

Now add the physical bouncer line itself: a stack of future day indices and a right-to-left loop. For now, each inspected day simply joins the line after its turn.

This step does not answer any nonzero waits yet. Its job is to establish the direction of travel and the idea that earlier days are querying a structure built from the future.

Hints & gotchas

• Scan from right to left: the stack is supposed to represent future days, so the future must already be built when you inspect a day.
• Store indices, not temperatures: the final answer needs day gaps like nextWarmerDay - day.
• Push after inspection: the current day should become part of the future only for earlier days.

Step 3: Use an Obviously Warmer Top Day

Before the full cleanup rule exists, there is still one easy case you can already solve: if the top of futureLine is immediately warmer than the current day, that top index is the answer.

This step teaches how the stack turns an index into a wait count. It works on inputs where the nearest future day is already the right answer, like steadily rising temperature runs.

Hints & gotchas

• Measure index distance: the wait is futureDayIndex - day, not a temperature difference.
• Check that the top is truly warmer: a future day that is cooler or equal cannot answer the question.
• This step is intentionally limited: it handles direct warmer neighbors and rising runs, not blocked candidates yet.

Step 4: Kick Out Blocked Days First

Now teach the full monotonic rule. Before reading the answer, pop every future day whose temperature is less than or equal to temperatures[day]. Those blocked days can never be the first warmer answer for this day or any earlier day.

After cleanup, the top of the line is finally trustworthy. If it exists, it is the nearest true warmer day. If the line is empty, the default 0 stays.

Hints & gotchas

• Use <=, not <: an equal-temperature future day is not warmer, so it must be removed too.
• Cleanup happens before reading the answer: otherwise you may measure the gap to a day that is too cool to help.
• Push after answering: the current day becomes part of the future line only for earlier days.

Common Misconceptions

"I should store temperatures directly in the stack." That loses the day distance. The stack needs indices so you can compute nextWarmerDay - day.

"An equal temperature should count as warmer enough." The problem says warmer, not warmer-or-equal. Equal temperatures must be popped away just like cooler ones.

"The stack should keep every future day." No. The whole optimization comes from removing future days that have already been made irrelevant by a nearer, hotter day.

"I should scan from left to right because the array is written that way." Left-to-right makes you search for the future before you have organized it. Right-to-left lets the stack already represent the future when each day asks its question.

Complete Solution