Daily Temperatures LeetCode Problem 739 [Python Solution]

In Daily Temperatures LeetCode Problem, we are given an array of integers representing daily temperatures.

The task is to return an array, answer, where each element at index i represents the number of days one has to wait after the ith day to find a warmer temperature.

If no warmer temperature is found in the future, the corresponding element in answer should be 0.

Example:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Understanding Constraints

Before delving into the solution, let’s understand the constraints provided in the problem:

• The length of the temperatures array will be between 1 and 105.
• The temperatures in the array will be between 30 and 100.

Efficient Solution

To solve this problem efficiently, we can use a monotonic decreasing stack. Here’s how it works:

1. We initialize an empty list, stack, to keep track of the temperatures and their corresponding indices.
2. We iterate through the temperatures array from left to right.
3. For each temperature, we check if the stack is empty or if the current temperature is greater than the temperature at the top of the stack.

• If the stack is not empty and the current temperature is greater, we pop elements from the stack, calculate the number of days it took to find a warmer temperature, and update the corresponding positions in the answer array.

1. Finally, we add the current temperature and its index to the stack.

Daily Temperatures LeetCode Solution in Python

Here’s the Python code for the efficient solution:

def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # A stack to keep track of temperatures and their indices

    for i in range(n):
        while stack and temperatures[i] > stack[-1][0]:
            temp, index = stack.pop()
            answer[index] = i - index
        stack.append((temperatures[i], i))

    return answer

This solution has a time complexity of O(n) and a space complexity of O(n) due to the stack.

Reasoning Behind Our Approach

The reason this approach works is that we maintain a stack of temperatures in decreasing order.

When a higher temperature is encountered, we know how many days it took to find a warmer temperature for the elements in the stack.

We keep popping from the stack until we find a temperature greater than the current one, and for each pop, we update the answer array with the corresponding number of days.

Related Interview Questions

• Container With Most Water LeetCode Problem
• Valid Parentheses LeetCode Problem
• 3Sum LeetCode Problem
• Generate Parentheses LeetCode Problem
• Car Fleet LeetCode Problem

Conclusion

In this blog post, we tackled the LeetCode problem “Daily Temperatures” (Problem 739) using an efficient algorithm.

By maintaining a monotonic decreasing stack, we were able to find the number of days one needs to wait for a warmer temperature after each day.

This solution runs in linear time and provides a space-efficient solution to the problem.

If you have any questions, suggestions, or comments, feel free to share them in the comments section.

LeetCode Problem Link

Happy coding!