Days Until Warmer
MediumStack
Problem
A weather station logs one temperature per day in temps. For each day, report how many days you would wait for a strictly warmer day.
Return an array wait where wait[i] is the number of days from day i to the first later day with a higher temperature, or 0 if no such day exists.
Example 1
- Input:
- temps = [30, 32, 31, 29, 35, 30]
- Output:
- [1, 3, 2, 1, 0, 0]
Day 1 (32) waits until day 4 (35): 3 days. Day 4 is never beaten, and day 5 is the last day.
Example 2
- Input:
- temps = [50, 50, 50]
- Output:
- [0, 0, 0]
Equal is not warmer.
Constraints
- 1 ≤ temps.length ≤ 10^5
- -100 ≤ temps[i] ≤ 10^4
Hint
Show the first hint
Think about the days that are still waiting for an answer. What do their temperatures look like, in order?
Walkthrough
How to approach it
01Clarify before coding
- Strictly warmer or warmer-or-equal? Strictly: equal temperatures do not count.
- What if no warmer day comes? Report 0.
- Do I return distances or indices? Distances (number of days to wait).
02Brute force
For each day i, scan forward until a warmer day appears.
Cost: O(n²) in the worst case (a long cooling trend followed by one hot day): 5·10^9 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.