Daily Temperatures
For each day, find how many days until a warmer temperature.
For each day, return how many days you must wait until a warmer temperature. This is the cleanest next-greater-element pattern on indices.
Pattern fit
Each day wants the next strictly greater value on the right, which is the most textbook monotonic-stack trigger.
Key observation
Store unresolved indices in a decreasing stack; the current warmer day resolves all smaller temperatures behind it.
Target complexity
O(n) / O(n)
How to break down the solution cleanly
Keep a stack of unresolved day indices in decreasing temperature order.
When a warmer day arrives, it resolves every smaller temperature on the stack top.
Pop resolved indices and fill their waiting-day distance immediately.
Push the current index after all smaller temperatures are handled.
Walk through one example
Example: [73, 74, 75, 71, 69, 72, 76, 73].
74 resolves 73, so answer[0] = 1; 75 resolves 74, so answer[1] = 1.
72 later resolves 69 and 71, then 76 resolves 72 and 75.
Indices left on the stack never see a warmer future day, so they stay 0.
Reference implementation
Pythondef dailyTemperatures(temperatures: list[int]) -> list[int]:
answer = [0] * len(temperatures)
stack: list[int] = []
for index, value in enumerate(temperatures):
while stack and temperatures[stack[-1]] < value:
previous = stack.pop()
answer[previous] = index - previous
stack.append(index)
return answer
Common pitfalls
Storing values instead of indices and losing distance information.
Using <= when the problem requires strictly warmer temperatures.
Common follow-ups
Why is each index pushed and popped at most once?
How would a next smaller version differ?
Continue with related problems
Build repeatable depth inside the Monotonic Stack cluster before moving on.