LeetCode 739: Daily Temperatures

Problem Restatement

We are given an array temperatures.

Each value represents the temperature on one day.

For every day i, we need to find how many days we must wait until a future day has a strictly warmer temperature.

If no warmer future day exists, the answer for that day is 0.

The official problem asks for an array answer where answer[i] is the number of days after day i until a warmer temperature appears. If no such day exists, keep answer[i] = 0.

Input and Output

Example function shape:

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    ...

Examples

Example 1

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

The answer is:

[1, 1, 4, 2, 1, 1, 0, 0]

For day 0, temperature is 73.

The next warmer day is day 1, where temperature is 74.

So:

answer[0] = 1

For day 2, temperature is 75.

The next warmer day is day 6, where temperature is 76.

So:

answer[2] = 6 - 2 = 4

Example 2

temperatures = [30, 60, 90]

Each day except the last has a warmer day immediately after it.

The answer is:

[1, 1, 0]

Example 3

temperatures = [90, 60, 30]

No day has a warmer future day.

The answer is:

[0, 0, 0]

First Thought: Check Future Days

The direct solution is simple.

For each day i, scan all later days j.

The first time we find:

temperatures[j] > temperatures[i]

we set:

answer[i] = j - i

This works, but it can be slow.

If the temperatures are mostly decreasing, each day may scan almost the whole remaining array.

That gives O(n^2) time.

Key Insight

This is a next greater element problem.

For each index, we want the nearest future index with a larger value.

A monotonic stack keeps unresolved days.

We scan from left to right.

The stack stores indices of days that have not found a warmer future day yet.

The temperatures at those indices are kept in decreasing order from bottom to top.

When the current temperature is warmer than the temperature at the stack top, the current day is the answer for that earlier day.

Algorithm

Create:

answer = [0] * len(temperatures)
stack = []

The stack stores indices.

For each index i and temperature temp:

1. While the stack is not empty and temp > temperatures[stack[-1]]:
   • Pop the previous index prev.
   • Set answer[prev] = i - prev.
2. Push i onto the stack.

At the end, every index still in the stack has no warmer future day, so its answer remains 0.

Correctness

The stack contains indices whose next warmer day has not been found yet.

When we process day i, if temperatures[i] is greater than the temperature at the stack top, then day i is a warmer future day for that stacked index.

It is also the nearest warmer future day. If there had been an earlier warmer day between the stacked index and i, that earlier day would already have popped the index from the stack.

So assigning:

answer[prev] = i - prev

is correct.

If the current temperature is not warmer than the stack top, it cannot answer that day or any colder relationship blocked behind it yet. We push the current index and wait for a future warmer day.

Every index is pushed once. It is popped only when its first warmer future day is found. If it is never popped, no warmer future day exists, and its answer correctly remains 0.

Therefore the algorithm returns the correct waiting time for every day.

Complexity

Let n = len(temperatures).

Implementation

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        answer = [0] * len(temperatures)
        stack = []

        for i, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                prev = stack.pop()
                answer[prev] = i - prev

            stack.append(i)

        return answer

Code Explanation

We initialize all answers to 0:

answer = [0] * len(temperatures)

This is correct by default for days that never find a warmer future day.

The stack stores indices, not temperatures:

stack = []

We need indices so we can compute the distance:

i - prev

For each day:

for i, temp in enumerate(temperatures):

we resolve all previous colder days:

while stack and temp > temperatures[stack[-1]]:

When a previous day is popped:

prev = stack.pop()
answer[prev] = i - prev

the current day is the first warmer future day for prev.

Finally, the current day waits for its own future warmer day:

stack.append(i)

Testing

def run_tests():
    s = Solution()

    assert s.dailyTemperatures(
        [73, 74, 75, 71, 69, 72, 76, 73]
    ) == [1, 1, 4, 2, 1, 1, 0, 0]

    assert s.dailyTemperatures([30, 60, 90]) == [1, 1, 0]
    assert s.dailyTemperatures([90, 60, 30]) == [0, 0, 0]
    assert s.dailyTemperatures([70]) == [0]
    assert s.dailyTemperatures([70, 70, 71]) == [2, 1, 0]
    assert s.dailyTemperatures([71, 70, 70]) == [0, 0, 0]

    print("all tests passed")

run_tests()