Given an array of daily temperatures, return an array where answer[i] is the number of days until a warmer temperature. Use a monotonic decreasing stack of indices.
TimeO(n)each index pushed/popped once
SpaceO(n)stack
Index: —Stack: []
Current
In Stack
Answered
Default
answer[]
—
Stack
[]
Ready
Press Play. Scan left to right: pop stack while current temp > top, push current index. Monotonic decreasing stack.
TimeO(n²)nested loops
SpaceO(1)no extra structure
Brute force: for each day i, scan forward to find the first warmer day j. answer[i] = j − i. O(n²) worst case.
✎ Whiteboard
3
⌨ Type It
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
═══ DAILY TEMPERATURES — MONOTONIC STACK ═══
PATTERN ▸ Monotonic decreasing stack of indices O(n) · O(n)