For each day, how many days until a warmer temperature?

How to think about it

Recognise the pattern

“For each element, find the next greater element to its right” is the monotonic stack pattern. You see it whenever you need the nearest index that satisfies a comparison — next warmer day, next taller building, next larger price. The stack maintains a window of “still waiting” candidates in a useful order.

Build the approach step by step

Brute force: for each day i, scan forward until you find a warmer day. O(n²) — too slow for large inputs.

Monotonic stack:

The key observation: if day 3 is colder than day 2, day 2’s answer cannot come before day 3’s answer. We can process them together when we finally hit a warm-enough day.

Keep a stack of indices of days whose warmer future day we have not yet found, in decreasing temperature order (hence monotonic decreasing). When we process day i:

1. While the stack is not empty and temps[i] > temps[stack[-1]]: the day at the top has found its answer. Pop it, record answer[popped] = i - popped.
2. Push i onto the stack.

Anything still on the stack at the end gets answer = 0.

temps = [73, 74, 75, 71, 69, 72, 76, 73]
i=0: stack=[0]
i=1: 74>73 -> pop 0, ans[0]=1; stack=[1]
i=2: 75>74 -> pop 1, ans[1]=1; stack=[2]
i=3: 71<75, stack=[2,3]
i=4: 69<71, stack=[2,3,4]
i=5: 72>69 -> pop 4, ans[4]=1; 72>71 -> pop 3, ans[3]=2; stack=[2,5]
i=6: 76>72 -> pop 5, ans[5]=1; 76>75 -> pop 2, ans[2]=4; stack=[6]
i=7: 73<76, stack=[6,7]
end: ans[6]=0, ans[7]=0

Complexity

	Value	Why
Time	O(n)	Each index is pushed and popped at most once
Space	O(n)	Stack holds at most n indices

Despite the nested while loop, each element is processed at most twice total across all iterations — this is an amortised O(n) argument.