Days Until a Warmer Day

A weather app has the daily temperatures. For every day, tell how many days you must wait for a strictly warmer temperature. If there is no warmer day in the future, the answer for that day is 0.

Examples

Example 1

Input:  temps = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

Day 0 (73) is followed at once by 74, so it waits 1 day. Day 2 (75) has to wait until day 6 (76), which is 4 days later. The last two days never see anything warmer, so they get 0, giving [1, 1, 4, 2, 1, 1, 0, 0].

Example 2

Input:  temps = [30, 40, 50, 60]
Output: [1, 1, 1, 0]

Constraints

temps holds one temperature per day, in order.

For each day return how many days later the first strictly warmer day comes, or 0 when no later day is warmer. The answer has one entry per day.

How to solve it

Hint

“Next greater element to the right” → keep a stack of days still waiting for a warmer day (temperatures on the stack are non-increasing). A new warmer day resolves all cooler days on top.

Approach: Monotonic stack (next greater element)

Stack holds indices whose answer is unknown.
For each day i: while the stack top has a smaller temperature, pop j and set answer[j] = i − j.
Push i.

Check with the example. Day 0 (73) waits 1 day for 74; day 2 (75) waits 4 days for 76.

Complexity: O(n) time (each index is pushed and popped once).

The reference solutions in all four languages are in the Solutions tab of the workspace below.