Daily Temperatures – Solution & Complexity
Solution Walkthrough
Step 1: Track unanswered days
- Each day wants the next future day with a higher temperature.
- If you scan left to right, some earlier days stay unanswered until a later warmer temperature arrives.
Step 2: Brute-force baseline
- For every index, scan forward until you find a warmer temperature or reach the end.
- That is simple but costs
O(n^2)in the worst case.
Step 3: Monotonic stack insight
- Keep a stack of indices whose warmer answer has not been found yet.
- Maintain it so temperatures are decreasing from bottom to top.
- When a new temperature is warmer than the stack top, pop indices until the invariant is restored; each popped index gets its answer immediately.
Step 4: Final solution (all languages)
Each index is pushed once and popped once, so the monotonic-stack scan is linear.
Step 5: Common mistakes and follow-ups
- Using
<=instead of<when comparing temperatures, which incorrectly treats equal temperatures as warmer. - Storing temperatures in the stack instead of indices, which loses the distance information needed for the answer.
- Follow-up: for the previous warmer day, scan in the opposite direction or maintain a stack of candidates to the left.
- Using
