LeetCode 739 - Daily Temperatures

The problem gives an array called temperatures, where each element represents the temperature recorded on a specific day. For every day, we must determine how many days in the future we need to wait until a warmer temperature appears.

leetcodemediumarraystackmonotonic-stack

LeetCode Problem 739

Difficulty: 🟡 Medium
Topics: Array, Stack, Monotonic Stack

Solution

Problem Understanding

The problem gives an array called temperatures, where each element represents the temperature recorded on a specific day. For every day, we must determine how many days in the future we need to wait until a warmer temperature appears. If there is no future day with a higher temperature, the answer for that position should be 0.

In simpler terms, for each index i, we want to find the first index j such that:

j > i and temperatures[j] > temperatures[i]

The value stored in the result array at position i should then be:

j - i

If no such j exists, the result remains 0.

For example, consider:

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

For the first day, temperature 73, the next warmer temperature is 74 on the following day, so the answer is 1.

For the day with temperature 75, the next warmer temperature is 76, which occurs four days later, so the answer is 4.

The constraints are important:

1 <= temperatures.length <= 100000
30 <= temperatures[i] <= 100

The array can contain up to 10^5 elements, which means an inefficient nested-loop solution may become too slow. An O(n^2) algorithm could require billions of comparisons in the worst case. This strongly suggests we need a linear or near-linear solution.

Several edge cases are important to recognize early:

  • A strictly decreasing array such as [90,80,70], where every answer is 0
  • A strictly increasing array such as [30,40,50], where every answer except the last is 1
  • Repeated temperatures such as [70,70,70], where equal values do not count as warmer
  • A single-element array, where the answer must always be [0]

The problem guarantees that the input array is non-empty and that all temperatures are within a small valid range.

Approaches

Brute Force Approach

The most direct solution is to examine each day independently and search forward until a warmer temperature is found.

For every index i, we iterate through all future indices j > i. As soon as we encounter a temperature greater than temperatures[i], we store j - i in the answer array and stop searching for that day.

This approach is correct because it explicitly checks every possible future day in order, ensuring the first warmer day is found.

However, the performance is poor in the worst case. Consider a decreasing sequence like:

[100,99,98,97,...]

For the first element, we scan nearly the entire array. For the second, we scan almost the entire remaining array again. This repeated work leads to quadratic time complexity.

With up to 100000 elements, an O(n^2) solution is too slow.

Optimal Approach, Monotonic Stack

The key observation is that when searching for the next warmer day, we repeatedly compare temperatures against future values. Many of these comparisons are redundant.

Instead of repeatedly scanning forward, we can maintain a stack of indices whose warmer temperature has not yet been found.

The stack is kept in decreasing temperature order. This is why the structure is called a monotonic decreasing stack.

As we process each temperature:

  • If the current temperature is higher than the temperature at the top of the stack, we have found the next warmer day for the index on the stack.
  • We repeatedly pop from the stack while the current temperature is warmer.
  • For each popped index, the answer becomes the difference between the current index and the popped index.
  • After resolving all smaller temperatures, we push the current index onto the stack.

This works because each index enters and leaves the stack at most once, producing an O(n) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) For each day, scan forward until a warmer temperature is found
Optimal O(n) O(n) Uses a monotonic decreasing stack to avoid repeated scans

Algorithm Walkthrough

  1. Create a result array initialized with zeros.

Every position starts as 0 because if no warmer day exists, the answer should remain 0. 2. Create an empty stack to store indices.

We store indices instead of temperatures because we eventually need to calculate the distance between days. 3. Iterate through the temperatures array from left to right.

At each step, the current index represents a future day relative to all indices already stored in the stack. 4. While the stack is not empty and the current temperature is greater than the temperature at the index on top of the stack, resolve that waiting day.

This means we have finally found a warmer temperature for the day stored at the top of the stack. 5. Pop the top index from the stack.

Let this popped index be previous_index. 6. Compute the waiting time.

The number of waiting days is:

current_index - previous_index

Store this value in the answer array. 7. Continue popping while the current temperature is warmer than the stack top.

One current temperature may resolve multiple earlier days. 8. Push the current index onto the stack.

This day now waits for a future warmer temperature. 9. After processing the entire array, any indices still in the stack have no warmer future day.

Their answers correctly remain 0.

Why it works

The stack always maintains indices in decreasing temperature order. Any index remaining in the stack has not yet encountered a warmer future temperature.

When a warmer temperature appears, it immediately resolves the nearest unresolved colder day. Since indices are processed from left to right, the first warmer temperature encountered is guaranteed to be the correct answer.

Each index is pushed once and popped once, ensuring both correctness and efficiency.

Python Solution

from typing import List

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

        # Result array initialized with 0
        answer = [0] * n

        # Stack stores indices
        stack = []

        for current_index, current_temp in enumerate(temperatures):

            # Resolve all colder previous temperatures
            while stack and current_temp > temperatures[stack[-1]]:
                previous_index = stack.pop()
                answer[previous_index] = current_index - previous_index

            # Current day waits for a warmer future day
            stack.append(current_index)

        return answer

The implementation begins by creating the result array filled with zeros. This matches the problem requirement because any day without a warmer future temperature should remain 0.

The stack stores indices rather than raw temperatures. This is important because the final answer requires the distance between indices, not merely the temperature comparison.

The loop processes temperatures from left to right using enumerate, which gives both the current index and temperature.

Inside the loop, the while condition checks whether the current temperature is warmer than the temperature represented by the index at the top of the stack. If it is, we pop that index because we have found its next warmer day.

The waiting time is computed using:

current_index - previous_index

After resolving all colder temperatures, the current index is pushed onto the stack so future temperatures can potentially resolve it.

At the end, unresolved indices remain 0, which is already correct because the answer array was initialized with zeros.

Go Solution

func dailyTemperatures(temperatures []int) []int {
	n := len(temperatures)

	// Result array initialized with 0
	answer := make([]int, n)

	// Stack stores indices
	stack := []int{}

	for currentIndex, currentTemp := range temperatures {

		// Resolve all colder previous temperatures
		for len(stack) > 0 &&
			currentTemp > temperatures[stack[len(stack)-1]] {

			previousIndex := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			answer[previousIndex] = currentIndex - previousIndex
		}

		// Current day waits for a warmer future day
		stack = append(stack, currentIndex)
	}

	return answer
}

The Go implementation follows the same logic as the Python version. The primary difference is stack management.

Go does not have a built-in stack type, so a slice is used instead. Pushing is done with append, and popping is performed by slicing off the last element.

The result slice is initialized using:

make([]int, n)

which automatically fills it with zeros.

There are no integer overflow concerns because the maximum index difference is at most 100000, well within Go's integer range.

Worked Examples

Example 1

Input: [73,74,75,71,69,72,76,73]
Step Current Temp Stack Before Action Answer
0 73 [] Push 0 [0,0,0,0,0,0,0,0]
1 74 [0] 74 > 73, pop 0, answer[0]=1 [1,0,0,0,0,0,0,0]
1 74 [] Push 1 [1,0,0,0,0,0,0,0]
2 75 [1] 75 > 74, pop 1, answer[1]=1 [1,1,0,0,0,0,0,0]
2 75 [] Push 2 [1,1,0,0,0,0,0,0]
3 71 [2] Push 3 [1,1,0,0,0,0,0,0]
4 69 [2,3] Push 4 [1,1,0,0,0,0,0,0]
5 72 [2,3,4] 72 > 69, pop 4, answer[4]=1 [1,1,0,0,1,0,0,0]
5 72 [2,3] 72 > 71, pop 3, answer[3]=2 [1,1,0,2,1,0,0,0]
5 72 [2] Push 5 [1,1,0,2,1,0,0,0]
6 76 [2,5] 76 > 72, pop 5, answer[5]=1 [1,1,0,2,1,1,0,0]
6 76 [2] 76 > 75, pop 2, answer[2]=4 [1,1,4,2,1,1,0,0]
6 76 [] Push 6 [1,1,4,2,1,1,0,0]
7 73 [6] Push 7 [1,1,4,2,1,1,0,0]

Final output:

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

Example 2

Input: [30,40,50,60]
Step Current Temp Stack Before Action Answer
0 30 [] Push 0 [0,0,0,0]
1 40 [0] Pop 0, answer[0]=1 [1,0,0,0]
1 40 [] Push 1 [1,0,0,0]
2 50 [1] Pop 1, answer[1]=1 [1,1,0,0]
2 50 [] Push 2 [1,1,0,0]
3 60 [2] Pop 2, answer[2]=1 [1,1,1,0]

Final output:

[1,1,1,0]

Example 3

Input: [30,60,90]
Step Current Temp Stack Before Action Answer
0 30 [] Push 0 [0,0,0]
1 60 [0] Pop 0, answer[0]=1 [1,0,0]
1 60 [] Push 1 [1,0,0]
2 90 [1] Pop 1, answer[1]=1 [1,1,0]

Final output:

[1,1,0]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is pushed and popped from the stack at most once
Space O(n) The stack may contain up to all indices in the worst case

The important observation is that although the algorithm contains a nested while loop, each element can only be removed from the stack once. This means the total number of stack operations across the entire execution is linear.

In the worst case, such as a strictly decreasing array, all indices remain in the stack, requiring O(n) additional space.

Test Cases

from typing import List

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

        for current_index, current_temp in enumerate(temperatures):
            while stack and current_temp > temperatures[stack[-1]]:
                previous_index = stack.pop()
                answer[previous_index] = current_index - previous_index

            stack.append(current_index)

        return answer

solution = Solution()

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

# Strictly increasing temperatures
assert solution.dailyTemperatures([30,40,50,60]) == [1,1,1,0]

# Another increasing sequence
assert solution.dailyTemperatures([30,60,90]) == [1,1,0]

# Strictly decreasing temperatures
assert solution.dailyTemperatures([90,80,70,60]) == [0,0,0,0]

# All equal temperatures
assert solution.dailyTemperatures([70,70,70]) == [0,0,0]

# Single element array
assert solution.dailyTemperatures([50]) == [0]

# Mixed increasing and decreasing
assert solution.dailyTemperatures([70,71,70,72]) == [1,2,1,0]

# Warmer day far in the future
assert solution.dailyTemperatures([75,74,73,72,80]) == [4,3,2,1,0]

# Duplicate temperatures before warmer day
assert solution.dailyTemperatures([70,70,71]) == [2,1,0]

# Larger plateau
assert solution.dailyTemperatures([65,65,65,66]) == [3,2,1,0]
Test Why
[73,74,75,71,69,72,76,73] Standard mixed example
[30,40,50,60] Strictly increasing sequence
[30,60,90] Small increasing input
[90,80,70,60] Strictly decreasing sequence
[70,70,70] Equal temperatures are not warmer
[50] Smallest valid input
[70,71,70,72] Multiple stack pops in one iteration
[75,74,73,72,80] Warmest temperature appears late
[70,70,71] Duplicates before warmer temperature
[65,65,65,66] Long plateau followed by warmer day

Edge Cases

A strictly decreasing array is one of the most important edge cases. For example:

[90,80,70,60]

A naive implementation might accidentally search past array bounds or incorrectly reuse previous results. In the monotonic stack solution, every index remains in the stack because no warmer temperature ever appears. Since the answer array was initialized with zeros, the final result is automatically correct.

Equal temperatures are another common source of bugs. Consider:

[70,70,70]

The problem requires a strictly warmer temperature, not an equal one. This means the comparison must use > rather than >=. The implementation correctly keeps equal temperatures in the stack because equal values do not satisfy the warmer condition.

A single-element array is the smallest possible valid input:

[50]

There is no future day to compare against, so the answer must be [0]. The algorithm handles this naturally because the loop runs once, the index is pushed onto the stack, and no warmer day is ever found.

Another subtle case occurs when a warmer temperature resolves many previous days at once, such as:

[75,74,73,80]

When 80 is processed, the algorithm repeatedly pops indices from the stack and updates all corresponding answers. The while loop is essential here. Using only a single if statement would fail to resolve all pending colder temperatures correctly.