Daily Temperatures

Difficulty: Medium · Pattern: Monotonic Stack · Concept: General Coding (DSA) — Core Patterns to Drill

Largest Rectangle in a Skyline used a monotonic stack to compute an area. This problem applies the same stack discipline to a completely different question, the "next greater element" pattern: given a list of daily temperatures, for each day return how many days until a strictly warmer day, or 0 if none exists.

Your task: implement days_until_warmer(temps) in $O(n)$ time. Return a list the same length as temps.

Implement it yourself

assert days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
assert days_until_warmer([30, 40, 50, 60]) == [1, 1, 1, 0]
assert days_until_warmer([60, 50, 40, 30]) == [0, 0, 0, 0]
assert days_until_warmer([]) == []

Next: Design an LRU Cache