Repository navigation
055 — Daily Temperatures
LeetCode 739 · Medium. Given an array temperatures of daily temperatures, return an array answer such that answer[i] is the number of days you'd have to wait after day i to get a warmer temperature. If there is no future day for which this is possible, answer[i] = 0.
Picture standing in a line of people of different heights, each one waiting to find out "how many people ahead of me until someone taller shows up?" A naive approach has each person turn around and look forward one person at a time until they spot someone taller — exhausting if the line is long and mostly short. Here's the shortcut: keep a private lineup of "people still waiting for someone taller," standing shortest-you'd-still-need-to-answer at the very front. The instant a taller person walks up, everyone still waiting in that lineup who is shorter gets their answer immediately — "it's this many days away, right now" — and they leave the lineup for good, because they'll never need to keep waiting once they know the distance.
"How many days until a warmer day" is a textbook monotonic-stack cue: it's not just asking whether a next-greater element exists, it's asking for the distance to it. That's the signal to keep a stack of indices (not values) in decreasing-temperature order — when a warmer day finally arrives, the distance is just today's index − popped index, computed once, the moment it becomes knowable.
For each day, scan forward day by day until a warmer temperature turns up.
func dailyTemperaturesBruteForce(_ temperatures: [Int]) -> [Int] {
var result = [Int](repeating: 0, count: temperatures.count)
for i in 0..<temperatures.count {
for j in (i + 1)..<temperatures.count {
if temperatures[j] > temperatures[i] {
result[i] = j - i
break
}
}
}
return result
}Big-O: O(n²) time worst case — a strictly decreasing (or flat) sequence forces every day to scan all the way to the end without finding a warmer one. O(1) extra space (excluding the output array).
Keep a stack of indices whose temperatures are still waiting for a warmer day, kept in strictly decreasing order of temperature from bottom to top. When today's temperature beats the stack's top, that popped day has found its answer — resolve it and keep popping until today no longer beats the new top (or the stack empties). Then push today.
func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
var result = [Int](repeating: 0, count: temperatures.count)
var stack: [Int] = [] // indices; temperatures[stack] strictly decreasing bottom to top
for i in 0..<temperatures.count {
while let lastIndex = stack.last, temperatures[i] > temperatures[lastIndex] {
let waitingIndex = stack.removeLast()
result[waitingIndex] = i - waitingIndex
}
stack.append(i)
}
return result
}
// smoke test
print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
// [1, 1, 4, 2, 1, 1, 0, 0]Big-O: O(n) time — each index is pushed exactly once and popped at most once across the entire run, so total stack work is linear despite the nested-looking while. O(n) space for the stack in the worst case — a strictly decreasing temperature sequence never finds a warmer day, so nothing ever gets popped and every index stays on the stack until the end.
The brute force re-derives "how far to the next warmer day?" from scratch for every single day, rescanning days it's already implicitly seen from a previous day's scan. The optimal solution flips the direction of the work: instead of each day searching forward, each day arriving resolves every unresolved earlier day that it happens to beat, all at once. Because a day only ever gets resolved once — the instant a warmer day arrives — and only ever gets pushed once, the total number of pushes and pops across the whole array is bounded by 2n, giving the same "touch each element a constant number of times" linear guarantee that defines a Monotonic Stack.
- Monotonic Stack — the genuine pattern: a stack of indices kept in decreasing temperature order, each popped exactly once when its "next greater" is found — this problem is used as the canonical distance-to-next-greater example in that chapter.
- Stacks — the underlying LIFO structure holding the "still waiting for a warmer day" indices.
- Arrays & Strings — the input array being scanned and the output array being filled.
Daily Temperatures is a lineup of people waiting to hear "you'll wait exactly this many days" — the moment someone taller walks up, everyone shorter still waiting gets their answer at once and steps out of line for good.
For [73, 74, 75, 71, 69, 72, 76, 73], trace the stack's contents (as indices) after processing each day up through index 5 (temperature 72). At that point, which indices just got popped and resolved, and what values did they receive? Explain why index 3 (71) is not resolved by day 5's 72.