Daily Temperatures
MediumMonotonic stack of 'waiting' days
Keep a pile of days still waiting for a warmer day; a warm day answers all the cooler days below it.
The idea
Keep a stack of indices whose warmer day hasn't been found yet, with temperatures decreasing down the stack. A warmer day pops everything it beats, resolving their answers.
73
74
75
71
69
72
76
73
0
1
2
3
4
5
6
7
Step 1 of 13. Brute force: for each element, scan right until you find the next warmer day. Values: 73, 74, 75, 71, 69, 72, 76, 73.
1/13
Brute force
timeO(n²)spaceO(1)
Scan right each day.
1// for each day, scan ahead for a warmer one2for (let i = 0; i < n; i++)3 for (let j = i + 1; j < n; j++)4 if (T[j] > T[i]) { res[i] = j - i; break; }Input
- array
- [73, 74, 75, 71, 69, 72, 76, 73]
Memory
- i
- —
- j
- —
Output
- done
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- temps = [73, 74, 75, 71, 69, 72, 76, 73]
- Output:
- [1, 1, 4, 2, 1, 1, 0, 0]
- Explanation:
- Days to wait for a warmer day.
Example 2
- Input:
- temps = [30, 40, 50, 60]
- Output:
- [1, 1, 1, 0]
- Explanation:
- Each next day is warmer → all 1s (last 0).
Example 3
- Input:
- temps = [30, 20, 10]
- Output:
- [0, 0, 0]
- Explanation:
- It only cools → all 0s.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.