#739

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Daily Temperatures

In the Daily Temperatures problem, you need to find out how many days to wait for a warmer temperature based on given daily temperatures.

array stack monotonic stack

Problem Statement

You are given an array of integers, temperatures, where each element represents the temperature of a given day. For each day in the array, you need to determine how many days you need to wait to find a warmer temperature. If no warmer temperature exists in the future, the result should be 0 for that day.

The goal is to return an array, answer, where answer[i] represents the number of days you have to wait after the i-th day to get a warmer temperature. If no such day exists, answer[i] will be 0.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: temperatures = [30,40,50,60]

Output: [1,1,1,0]

Example details omitted.

Example 3

Input: temperatures = [30,60,90]

Output: [1,1,0]

Example details omitted.

Constraints

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

Solution Approach

Monotonic Stack Approach

The most efficient approach to solve this problem is using a stack. The stack will help manage the days in a way that we can always find the next warmer day. We push the index of each temperature onto the stack and check if the current temperature is warmer than the one at the index on top of the stack. If it is, we pop the stack and calculate the number of days to wait.

Iterate Through Temperatures

We loop through the temperatures array and for each temperature, compare it with the temperature at the top of the stack. If it’s warmer, we calculate the difference in days and continue processing until we find a suitable warmer day or exhaust the list.

Time and Space Complexity

The time complexity of the stack-based approach is O(n), where n is the number of days. Each index is pushed and popped from the stack once. The space complexity is O(n) because we store indices of the temperatures in the stack.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) due to the single pass through the temperatures array. Space complexity is O(n) because we use a stack to store indices of the temperatures.

What Interviewers Usually Probe

This problem tests the candidate’s ability to efficiently manage stack-based state in an array.
The candidate should demonstrate familiarity with monotonic stacks, a key pattern in algorithmic optimization.
The interviewer should look for a solution that optimizes both time and space complexities, ideally in O(n) time.

Common Pitfalls or Variants

Common pitfalls

A common mistake is not properly managing the stack and not popping elements at the correct time.
Another pitfall is inefficient time complexity, such as using nested loops instead of a single pass through the array.
Forgetting to return 0 when no warmer day exists is another error that can affect correctness.

Follow-up variants

Given the temperatures of multiple cities, find the days to wait for a warmer temperature for each city.
Use a similar approach to determine how many days you have to wait for a cooler temperature instead.
Modify the problem to return the actual temperature for each day, not just the number of days.

FAQ

What is the stack-based state management pattern?

The stack-based state management pattern uses a stack to maintain and process states, often used in problems where you need to compare elements or track changes over time, like finding the next warmer day.

How does the stack approach optimize the Daily Temperatures problem?

By using a monotonic stack, we can efficiently track the next warmer day in a single pass through the temperatures array, ensuring both time and space optimization.

What are the common mistakes when solving Daily Temperatures?

The common mistakes include failing to properly manage the stack, using inefficient time complexity, and forgetting to return 0 when no warmer day exists.

Can this problem be solved using a brute-force approach?

Yes, but it would have a time complexity of O(n^2), as it would involve nested loops to compare each day with every other day. The stack approach improves this to O(n).

What other variations of the Daily Temperatures problem exist?

Variations include finding the cooler days, determining the temperature on the waiting day, or handling multiple cities' temperature data in a similar way.

terminal

Solution

Solution 1: Monotonic Stack

This problem requires us to find the position of the first element greater than each element to its right, which is a typical application scenario for a monotonic stack.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stk = []
        n = len(temperatures)
        ans = [0] * n
        for i in range(n - 1, -1, -1):
            while stk and temperatures[stk[-1]] <= temperatures[i]:
                stk.pop()
            if stk:
                ans[i] = stk[-1] - i
            stk.append(i)
        return ans

Continue Practicing

#768 max chunks to make sorted ii #769 max chunks to make sorted #654 maximum binary tree