Daily Temperatures – Solution & Complexity

Watch: Daily Temperatures with a monotonic stack

Instead of each day scanning forward for a warmer one (O(n²)), keep a stack of the indices of days still waiting. Each new day pops every strictly colder day off the top and sets its answer to today's index minus the popped index, then pushes itself. The stack's temperatures never go up from bottom to top, so only the top needs checking. Days left on the stack stay 0. Each index is pushed once and popped at most once: O(n) time and space.

Solution Walkthrough

  1. Step 1: Track unanswered days

    • Each day wants the next future day with a higher temperature.
    • If you scan left to right, some earlier days stay unanswered until a later warmer temperature arrives.
  2. Step 2: Brute-force baseline

    • For every index, scan forward until you find a warmer temperature or reach the end.
    • That is simple but costs O(n^2) in the worst case.
  3. Step 3: Monotonic stack insight

    • Keep a stack of indices whose warmer answer has not been found yet.
    • Maintain it so temperatures are decreasing from bottom to top.
    • When a new temperature is warmer than the stack top, pop indices until the invariant is restored; each popped index gets its answer immediately.
  4. Step 4: Final solution (all languages)

    Each index is pushed once and popped once, so the monotonic-stack scan is linear.

    def daily_temperatures(temperatures: list[int]) -> list[int]:
        answer = [0] * len(temperatures)
        stack: list[int] = []
    
        for i, temperature in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < temperature:
                prev = stack.pop()
                answer[prev] = i - prev
            stack.append(i)
    
        return answer
  5. Step 5: Common mistakes and follow-ups

    • Using <= instead of < when comparing temperatures, which incorrectly treats equal temperatures as warmer.
    • Storing temperatures in the stack instead of indices, which loses the distance information needed for the answer.
    • Follow-up: for the previous warmer day, scan in the opposite direction or maintain a stack of candidates to the left.

FAQ