Days Until Warmer
Problem
You are given daily temperature readings in order. For each day, report how many days you must wait before a strictly warmer reading appears. Write 0 for any day that is never followed by a warmer one.
Examples
Input: temps = [30, 32, 31, 35]
Output: [1, 2, 1, 0]
Why: day 0 waits one day, day 1 waits until day 3, day 3 never warms upInput: temps = [40, 39, 38]
Output: [0, 0, 0]
Why: the readings only cool downInput: temps = [20]
Output: [0]
Why: edge case, a single day has no future at allHints
0 / 3
Looking ahead from every day rechecks the same later days over and over. Try flipping it around and asking which earlier days a given day answers.
Days still waiting for an answer pile up in a very specific order: each one is cooler than or equal to the one before it. That ordering suggests where to store them.
Walk the days once, keeping the positions of unanswered days on a stack. When the current reading is warmer than the reading at the top position, pop it and record the distance between the two positions. Repeat until the top is not cooler, then push the current position.
Solution
Positions of days still waiting for a warmer reading are held on a stack, and their temperatures always decrease from bottom to top. Each new day resolves every waiting day it beats by popping them and recording the gap between the positions. Any day left on the stack at the end never warms up and keeps its zero. Each position is pushed and popped at most once, so time is O(n) and space is O(n).
def days_until_warmer(temps):
out = [0] * len(temps) # unresolved days keep their zero
stack = [] # positions still waiting for warmth
for i, t in enumerate(temps):
# today resolves every waiting day it beats
while stack and temps[stack[-1]] < t:
j = stack.pop()
out[j] = i - j
stack.append(i)
return out
print(days_until_warmer([30, 32, 31, 35])) # -> [1, 2, 1, 0]
print(days_until_warmer([40, 39, 38])) # -> [0, 0, 0]
print(days_until_warmer([20])) # -> [0]Stuck on the idea rather than the code? Monotonic Stack covers it.