The tell: 'How many days until a warmer one' — a next-greater-element question.
How you get there
1Keep a stack of indices whose temperatures are decreasing.
2A warmer day resolves every colder index sitting above it on the stack.
3Each index is pushed once and popped at most once, so the total is linear.
Solution
Python
def daily_temperatures(temps: list[int]) -> list[int]:
out = [0] * len(temps)
stack: list[int] = [] # indices, temperatures decreasing
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
out[j] = i - j
stack.append(i)
return out
Time
O(n)
Space
O(n)
What goes wrong
Storing temperatures rather than indices loses the position needed to compute the gap.