Problem

We are given an array temperatures, where temperatures[i] represents the temperature on day i.

We need to return an array result, where result[i] tells us how many days we have to wait after day i to get a warmer temperature.

If there is no warmer temperature in the future, then result[i] should be 0.

Example

temperatures = [30, 38, 30, 36, 35, 40, 28]

Output:

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

Explanation:

• Day 0 has temperature 30. The next warmer day is day 1 with 38, so answer is 1.
• Day 1 has temperature 38. The next warmer day is day 5 with 40, so answer is 4.
• Day 2 has temperature 30. The next warmer day is day 3 with 36, so answer is 1.
• Day 3 has temperature 36. The next warmer day is day 5 with 40, so answer is 2.
• Day 4 has temperature 35. The next warmer day is day 5 with 40, so answer is 1.
• Day 5 has temperature 40. There is no warmer future day, so answer is 0.
• Day 6 has temperature 28. There is no future day, so answer is 0.

Approach 1: Brute Force

The simplest way to solve this problem is to check every future day for each current day.

For every temperature at index i, we look at the days after it using another pointer j.

If we find a day where:

temperatures[j] > temperatures[i]

then we know how many days we waited:

j - i

If we reach the end of the array and do not find a warmer day, we store 0.

Code

from typing import List 

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = []

        for i in range(n):
            count = 1
            j = i + 1

            while j < n and temperatures[j] <= temperatures[i]:
                count += 1
                j += 1

            if j == n:
                count = 0

            res.append(count)

        return res

Complexity

For each day, we may need to scan all future days.

Time complexity:

O(n^2)

Space complexity:

O(1)

The output array is not usually counted as extra space.

This solution works, but it is not the most efficient.

Approach 2: Monotonic Stack

A better solution is to use a stack.

The stack stores days that have not yet found a warmer temperature.

Each stack element contains:

(index, temperature)

We loop through the temperatures from left to right.

For each current temperature, we check whether it is warmer than the temperature at the top of the stack.

If it is warmer, that means we have found the answer for the day stored on top of the stack.

So we pop from the stack and update the result:

res[index] = i - index

We continue doing this while the current temperature is warmer than the top of the stack.

After that, we add the current day to the stack.

Code

from typing import List

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

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

            stack.append((i, temp))

        return res

Walkthrough

For this input:

temperatures = [30, 38, 30, 36, 35, 40, 28]

We start with:

res = [0, 0, 0, 0, 0, 0, 0]
stack = []

Day 0: temperature is 30.

Stack is empty, so we push:

stack = [(0, 30)]

Day 1: temperature is 38.

38 is warmer than 30, so day 0 waited:

1 - 0 = 1

Update:

res = [1, 0, 0, 0, 0, 0, 0]

Push day 1:

stack = [(1, 38)]

Day 2: temperature is 30.

30 is not warmer than 38, so push:

stack = [(1, 38), (2, 30)]

Day 3: temperature is 36.

36 is warmer than 30, so day 2 waited:

3 - 2 = 1

Update:

res = [1, 0, 1, 0, 0, 0, 0]

Push day 3:

stack = [(1, 38), (3, 36)]

Day 4: temperature is 35.

35 is not warmer than 36, so push:

stack = [(1, 38), (3, 36), (4, 35)]

Day 5: temperature is 40.

40 is warmer than 35, so day 4 waited 1 day.

40 is also warmer than 36, so day 3 waited 2 days.

40 is also warmer than 38, so day 1 waited 4 days.

Update:

res = [1, 4, 1, 2, 1, 0, 0]

Push day 5:

stack = [(5, 40)]

Day 6: temperature is 28.

28 is not warmer than 40, so push:

stack = [(5, 40), (6, 28)]

There are no more days left, so the remaining days in the stack have no warmer future day. Their result stays 0.

Final answer:

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

Why the Stack Works

The stack keeps track of temperatures that are waiting for a warmer day.

It is called a monotonic decreasing stack because temperatures in the stack are generally kept in decreasing order.

When we find a warmer temperature, we resolve all previous colder days.

This avoids checking the same days again and again.

Each index is pushed into the stack once and popped from the stack once.

Complexity

Time complexity:

O(n)

Space complexity:

O(n)

The stack may store up to all days in the worst case.

Final Thoughts

The brute force solution is easy to understand, but it can be slow because it checks future days repeatedly.

The monotonic stack solution is more efficient because it keeps track of unresolved days and updates them as soon as a warmer temperature appears.

For this problem, the monotonic stack approach is the best solution.