Pattern visualizer
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. Animated on: temperatures = [73,74,75,71,69,72,76,73] — compute days until a warmer day for each index..
Stack
i=0, t=73. Stack empty, push index 0. Stack: [0]. ans: [0]
1FUNCTION dailyTemperatures(temps):2 ans = an array of 0s, one per day3 stack = an empty stack of day indices4 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 stack7 ans[idx] = i - idx (days waited)8 push i onto the stack9 RETURN ans
← / → step · space play · Home restart