DSA Tracker

Visualize

Daily Temperatures

The key insight: an index only needs to sit and wait until a warmer day shows up, so instead of re-scanning forward from every day (O(n^2)), keep a stack of days that are still waiting. Keeping the stack's temperatures decreasing means every index still on it hasn't found its answer yet — the moment a warmer temperature arrives, it's the first warmer day for every smaller temperature still waiting below it, so they all resolve at once and get answer = current_index - popped_index. Each index is pushed and popped exactly once, giving O(n) total instead of a nested scan.

Details

Animated on: temperatures = [73,74,75,71,69,72,76,73] — compute days until a warmer day for each index.

Problem:Daily TemperaturesMedium

Pattern:Monotonic Stack

Stack

step 1 / 8

73
[0]

i=0, t=73. Stack empty, push index 0. Stack: [0]. ans: [0]

  • i=0· arr[0] = 73
Pseudocode
1FUNCTION dailyTemperatures(temps):
2  ans = an array of 0s, one per day
3  stack = an empty stack of day indices
4  FOR each day i with temperature t in temps:
5    WHILE the stack is not empty and temps[top of stack] < t:
6      idx = pop the top of the stack
7      ans[idx] = i - idx   (days waited)
8    push i onto the stack
9  RETURN ans

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. i=0, t=73. Stack empty, push index 0. Stack: [0]. ans: [0]
  2. i=1, t=74. temps[stack[-1]]=73 < 74, so pop idx=0. ans[0] = 1-0 = 1. Stack empty, push 1. Stack: [1]. ans: [1,0]
  3. i=2, t=75. temps[stack[-1]]=74 < 75, pop idx=1. ans[1] = 2-1 = 1. Stack empty, push 2. Stack: [2]. ans: [1,1,0]
  4. i=3, t=71. temps[stack[-1]]=75 >= 71, no pop. Push 3. Stack: [2, 3]. ans: [1,1,0,0]
  5. i=4, t=69. temps[stack[-1]]=71 >= 69, no pop. Push 4. Stack: [2, 3, 4]. ans: [1,1,0,0,0]
  6. i=5, t=72. temps[stack[-1]]=69 < 72, pop idx=4. ans[4] = 5-4 = 1. Now tops=temps[3]=71 >= 72? No, 71 < 72, so pop idx=3. ans[3] = 5-3 = 2. Now tops=temps[2]=75 >= 72, stop. Push 5. Stack: [2, 5]. ans: [1,1,0,2,1,0]
  7. i=6, t=76. temps[stack[-1]]=72 < 76, pop idx=5. ans[5] = 6-5 = 1. temps[stack[-1]]=75 < 76, pop idx=2. ans[2] = 6-2 = 4. Stack is now empty, stop popping. Push 6. Stack: [6]. ans: [1,1,4,2,1,1,0,0]
  8. i=7, t=73. temps[stack[-1]]=76 >= 73, no pop. Push 7. Stack: [6, 7]. ans: [1,1,4,2,1,1,0,0]. Final answer: days until warmer day for each index.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Daily Temperatures in the editorAll Stack problemsBack to roadmap