LeetCode 739 ·
Medium
Daily Temperatures
For each day, how many days until a warmer temperature (0 if none).
Try it
Step through the core mechanic. The simulator below runs the stack / monotonic stack shape this problem is built on.
Interactive · monotonic stack pop while the new value beats the top
input
73 0
74 1
75 2
71 3
69 4
72 5
76 6
73 7
stack (value@index)
empty
answer (days until warmer)
00000000
empty stack of indices (temperatures decreasing top→down)
The approach
A stack of indices with decreasing temperatures. When today is warmer than the stack top, pop and record the day gap. Each index is pushed and popped once, so it is O(n).
| Aspect | Value |
|---|---|
| Pattern | Stack / monotonic stack |
| Recognise it by | Days until a warmer day — next-greater-element. |
| Time complexity | O(n) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.