739. Daily Temperatures - Explanation

Description

You are given an array of integers temperatures where temperatures[i] represents the daily temperatures on the ith day.

Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the ith day, set result[i] to 0 instead.

Example 1:

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

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

Example 2:

Input: temperatures = [22,21,20]

Output: [0,0,0]

Constraints:

1 <= temperatures.length <= 1000.
1 <= temperatures[i] <= 100

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.

Hint 1

A brute force solution would involve iterating through the array with index i and checking how far is the next greater element to the right of i. This would be an O(n^2) solution. Can you think of a better way?

Hint 2

Can you consider a reverse approach? For example, in [2, 1, 1, 3], the next greater element for the numbers [2, 1, 1] is 3. Instead of checking for each element individually, can you think of a way where, by standing at the element 3, you compute the result for the elements [2, 1, 1]? Maybe there's a data structure that is useful here.

Hint 3

We can use a stack to maintain indices in a monotonically decreasing order, popping indices where the values are smaller than the current element. This helps us find the result by using the difference between indices while considering the values at those indices. Can you see how the stack is useful?

Hint 4

In the array [2, 1, 1, 3], we don't perform any pop operations while processing [2, 1, 1] because these elements are already in decreasing order. However, when we reach 3, we pop elements from the stack until the top element of the stack is no longer less than the current element. For each popped element, we compute the difference between the indices and store it in the position corresponding to the popped element.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

For each day, we simply look forward to find the next day with a higher temperature.
We compare the current day with every future day until we either find a warmer one or reach the end.
If we find a warmer day, we record how many days it took.
If not, the answer is 0.
This method is easy to understand but slow because every day may scan many days ahead.

Algorithm

Let res store the number of days until a warmer temperature.
For each index i:
- Start checking from the next day j = i + 1 and count how many steps it takes to find a warmer day.
- If a warmer day is found, store the count.
- Otherwise, store 0.
Return res.

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:
                if temperatures[j] > temperatures[i]:
                    break
                j += 1
                count += 1
            count = 0 if j == n else count
            res.append(count)
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output array.

2. Stack

Intuition

We want to know how long it takes until a warmer day for each temperature.
A stack helps because it keeps track of days that are still waiting for a warmer temperature.
As we scan forward, whenever we find a temperature higher than the one on top of the stack, it means we just discovered the “next warmer day” for that earlier day.
We pop it, compute the difference in days, and continue.
This way, each day is pushed and popped at most once, making the process efficient.

Algorithm

Create a result list filled with zeros.
Use a stack to store pairs of (temperature, index) for days that haven't found a warmer day yet.
Iterate through the temperature list:
- While the stack is not empty and the current temperature is warmer than the top of the stack:
  - Pop the top element.
  - Compute how many days passed and update the result.
- Push the current day onto the stack.
Return the filled result list.

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

        for i, t in enumerate(temperatures):
            while stack and t > stack[-1][0]:
                stackT, stackInd = stack.pop()
                res[stackInd] = i - stackInd
            stack.append((t, i))
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming

Intuition

Instead of checking every future day one by one, we can reuse previously computed answers.
If day j is not warmer than day i, we don’t need to move forward step-by-step — we can simply jump ahead by using the result already stored for day j.
This lets us skip many unnecessary comparisons.
By working backward and using these jumps, we efficiently find the next warmer day for each position.

Algorithm

Create a result list res filled with zeros.
Traverse the temperature list from right to left.
For each day i:
- Start with the next day j = i + 1.
- While j is within bounds and not warmer:
  - If res[j] is 0, there is no warmer day ahead → stop.
  - Otherwise, jump forward by res[j] days.
- If j is within bounds and warmer, set res[i] = j - i.
Return res.

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

        for i in range(n - 2, -1, -1):
            j = i + 1
            while j < n and temperatures[j] <= temperatures[i]:
                if res[j] == 0:
                    j = n
                    break
                j += res[j]

            if j < n:
                res[i] = j - i
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output array.