DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Daily Temperatures

mediumStack and queue

Problem statement

You get a list of daily temperature readings, one integer per day. For each day, work out how many days you would have to wait until a day that is strictly warmer. If no warmer day ever comes, the answer for that day is 0.

Return a list of the same length with these waiting times.

Examples

Example 1

Input: temperatures = [70, 68, 72, 71, 69, 75]

Output: [2, 1, 3, 2, 1, 0]

Explanation: Day 0 (70) waits until day 2 (72). Day 2 (72) waits until day 5 (75). Nothing after day 5 is warmer.

Example 2

Input: temperatures = [30, 40, 50, 20]

Output: [1, 1, 0, 0]

Explanation: 50 and 20 never see a warmer day later in the list.

Hints

Approach

Use a monotonic stack of indices, the same idea as Next Greater Element, but store positions so you can compute distances.

  1. Walk the days left to right.
  2. While the day on top of the stack is colder than today, pop it: today is its first warmer day, so its answer is today - that index.
  3. Push today's index. It now waits for its own warmer day.
  4. Days still on the stack at the end never got one, and keep their default 0.

The temperatures of the indices on the stack never increase from bottom to top. Each index is pushed and popped at most once, so the total work is linear even though there is a loop inside a loop.

ComplexityTime O(n)Space O(n)
Python
class Solution:
def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
answer = [0] * len(temperatures)
stack = [] # indices of days still waiting for a warmer day
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer # days left on the stack keep their 0

Follow-up questions

  • Return the temperature of the next warmer day instead of the wait.
  • What if readings arrive as a live stream and you must emit each answer as soon as it is known?

Frequently asked questions

The answer is a distance between two days, so you need to know where the waiting day was. With the index you can always look up its temperature too.

Count pops instead of loop iterations. Each index is popped at most once over the whole run, so all the while loops together do at most n pops.

It is the same question as "how many samples until this metric next goes above its current value?", which comes up when measuring how long a service stayed below a latency peak or how long a queue took to grow past a level.