mafeshsho8lmafeshsho8l
Get Started
All coding questions

Daily Temperatures

medium
NeetCode 150stackmonotonic-stackarrays

Problem

Given a list of daily temperatures, for each day return how many days you must wait until a warmer temperature. If no warmer day exists, the answer for that day is zero.

Examples

Input: temps = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Each value is the gap to the next warmer day.

Constraints

  • • 1 <= temps.length <= 10^5
  • • 30 <= temps[i] <= 100
Hints(tap to reveal)
  • 1. A monotonic decreasing stack of indices helps.
  • 2. When a warmer day arrives, resolve all cooler days waiting.
Optimal approach(spoiler)
  1. Keep a stack of indices whose answers are not yet known.
  2. For each new temperature, pop every index with a lower temperature.
  3. For each popped index, the wait is the current index minus it.
  4. Push the current index and continue.
  5. Each index is pushed and popped once, giving O(n) time.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor