Given daily temperatures, return an array where answer[i] is the number of days after day i until a warmer temperature, or 0 if there is none.
Before you code
Scanning forward from each day is O(n²) when temperatures fall for a long time. Instead, keep the days that are still waiting for a warmer day on a stack, and let each new day answer as many of them as it can.
Hints
- Push indexes, not temperatures, so that you can compute
i - j. - While the new temperature is strictly greater than the one at the top index, pop and record the answer.
- Equal temperatures don't count as warmer:
[30, 30, 30]answers all zeros. - Each index is pushed once and popped at most once, so the loop is O(n) overall.
Production & complexity notes
When solving Daily temperatures on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Deques and monotonic stacks to reinforce the underlying pattern.
What it practices
The monotonic stack, from Deques and monotonic stacks.