Daily Temperatures

For each day, find how many days pass before a warmer temperature.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Daily Temperatures: A decreasing stack keeps unresolved day indices until the first warmer temperature can pop them.

Input and goalFor each day, find how many days pass before a warmer temperature.

Initialize unanswered daysStart with answer=[0,0,0,0,0,0,0,0] and an empty waiting stack.

emptytop waiting day

temperatures[73, 74, 75, 71, 69, 72, 76, 73]layoutoldest to newestcurrentbefore day 0answer[0,0,0,0,0,0,0,0]actioninitialize

Recognize it

Look for the first later greater value or the waiting distance to it; those words suggest keeping unresolved indices until a new value is large enough to answer them.

Keep true

After each day is appended, waiting indices increase from bottom to top while their temperatures are non-increasing, and every popped index receives its first strictly warmer later day.

Reuse it

For next-greater or next-smaller problems, store unresolved indices in a monotonic stack; the first value that violates the monotonic order resolves every eligible item popped from the top.

Pattern: Decreasing stack.

Simple idea: The stack holds days still waiting for something warmer. A warmer new day finishes every colder day at the top.

def daily_temperatures(temperatures: list[int]) -> list[int]:
   answer = [0] * len(temperatures)
   waiting: list[int] = []

   for day, temperature in enumerate(temperatures):
      while waiting and temperatures[waiting[-1]] < temperature:
         earlier_day = waiting.pop()
         answer[earlier_day] = day - earlier_day
      waiting.append(day)

   return answer

Cost: $O(n)$ time and $O(n)$ space. Each index enters and leaves the stack once.