Stack
Monotonic stack: next greater
Why it matters
Forecast and market data often need the first later reading that crosses a threshold for every timestamp. Starting a new forward search at each reading repeats long stretches when values fall. For [73, 74, 75, 71, 69, 72, 76, 73], compute every next-warmer wait in O(n), not with a fresh scan from each day.
Example
Daily Temperatures
For each day, return how many days you wait until a strictly warmer temperature. Use 0 if none exists.
- Input
- temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
- Output
- [1, 1, 4, 2, 1, 1, 0, 0]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Daily Temperatures
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]→[1, 1, 4, 2, 1, 1, 0, 0]
The baseline, Scan forward from each day, is O(n²) · O(1). The better model below keeps this exact input and removes that bottleneck.
When 72 arrives in [73, 74, 75, 71, 69, 72, 76, 73], it resolves 69 and 71; 76 later resolves 72 and 75. Keeping unresolved days in decreasing order replaces the brute repeated forward scans.
After processing 75, the earlier 73 and 74 already have waits of 1, while day 2 at 75 remains unresolved. Push days 3 and 4 for 71 and 69 above it, leaving unresolved temperatures in decreasing order.
At day 5, 72 pops day 4's 69 and records 1, then pops day 3's 71 and records 2; it stops below 75. Day 6 at 76 later resolves 72 with 1 and 75 with 4. Every day is pushed once and removed at most once.
Visual anchor
Daily Temperatures
answer
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.