Medium
Monotonic Stack
Daily Temperatures
A decreasing stack of indices resolves each 'next warmer day' exactly once.
Approach
Keep a stack of indices with decreasing temperatures. When a warmer day arrives, pop every colder index and record the day gap for each. Each index is pushed and popped once, so the whole thing is linear.
Time complexity
O(n)
Space complexity
O(n)
Common mistake
Scanning forward for each day (O(n²)) instead of letting the monotonic stack resolve answers as it pops.
See it run, step by step
Generate an interactive lesson for Daily Temperatures — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Daily Temperatures