Daily Temperatures
Understand the problem
Given an array temps of daily temperatures. For each day, return the number of days you have to wait until a warmer day. If no warmer day comes later, put 0.
Example:
temps = [73, 74, 75, 71, 69, 72, 76, 73]
output = [ 1, 1, 4, 2, 1, 1, 0, 0]
// day 0 (73°) waits 1 day to reach 74°; day 2 (75°) waits until day 6 (76°) = 4 daysShow the basic approach (slower)
O(n²) time, O(1) spacefunction dailyTemperatures(temps: number[]): number[] {
const res = new Array(temps.length).fill(0)
for (let i = 0; i < temps.length; i++) {
for (let j = i + 1; j < temps.length; j++) {
if (temps[j] > temps[i]) { res[i] = j - i; break }
}
}
return res
}For each day, scan all the days after it to find a warmer one.
For a decreasing array (every day has to scan to the end), the number of comparisons is about n²/2 — slow for large n.
Optimal solution
O(n) time, O(n) spacefunction dailyTemperatures(temps: number[]): number[] {
const res = new Array(temps.length).fill(0)
const stack: number[] = [] // indices; temperatures decrease from bottom to top
for (let i = 0; i < temps.length; i++) {
while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
const prev = stack.pop()!
res[prev] = i - prev
}
stack.push(i)
}
return res
}The optimal solution uses a monotonic stack to hold the indices of days that haven't found a warmer day yet, with temperatures decreasing.
- Each new, warmer day "resolves" all the pending days at the top of the stack.
- Every index is pushed and popped exactly once → O(n) in total.
Step-by-step trace
1function dailyTemperatures(temps: number[]): number[] {2 const res = new Array(temps.length).fill(0)3 const stack: number[] = [] // indices; temperatures decrease from bottom to top4 for (let i = 0; i < temps.length; i++) {5 while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {6 const prev = stack.pop()!7 res[prev] = i - prev8 }9 stack.push(i)10 }11 return res12}Edge cases to remember
Strictly decreasing array ([76, 75, 74]) — no later day is warmer, every element = 0; the stack only grows and never pops.
Two equal days (temps[j] === temps[i]) — NOT counted as warmer; use
>not>=, otherwise the answer is wrong.Increasing array ([70, 71, 72]) — each day immediately resolves the day before it, so the result is all 1s except the last element.
Single-element array → return [0].