Jobs

Interviews

Discussions

Daily Temperatures

Medium

Netflix

5 views

Topics:

ArraysStacks

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

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]

Constraints:

1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

Daily Temperatures

Medium

Netflix

5 views

Topics:

ArraysStacks

Example 1:

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]

Constraints:

1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of temperature values in the input array?
What is the maximum possible length of the `temperatures` array?
If a warmer temperature never occurs after a given day, should the corresponding element in the result array be 0?
Is the input array guaranteed to be non-empty?
Can I assume the input will always be valid, or should I handle potential null or invalid inputs?

Brute Force Solution

Approach

We want to find out, for each day, how many days we have to wait until a warmer day arrives. The brute force way to solve this is to simply check every single future day for each day we're considering.

Here's how the algorithm would work step-by-step:

For each day on the list, we will start looking at all the days that come after it.
We will compare the temperature of the current day with the temperature of each following day, one by one.
If we find a day that's warmer, we count how many days it took to get there and remember that number.
If we get to the end of the list without finding a warmer day, we know the answer for that day is zero.
We repeat this process, looking at every single day to see when the next warmer day is.

Code Implementation

def daily_temperatures_brute_force(temperatures):
    number_of_days = len(temperatures)
    days_to_warmer = [0] * number_of_days

    for current_day in range(number_of_days):
        # Iterate through each day to find warmer temperature.

        for future_day in range(current_day + 1, number_of_days):
            # Compare current day's temp with each subsequent day.
            if temperatures[future_day] > temperatures[current_day]:
                days_to_warmer[current_day] = future_day - current_day
                break

        # If no warmer day is found, the default value remains 0

    return days_to_warmer

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each day's temperature in the input array of size n. For each of these days, it potentially iterates through the remaining days to find a warmer temperature. In the worst case, for each day, we might compare it with all subsequent days. Therefore, the number of comparisons is proportional to n * (n-1)/2, which simplifies to O(n²).

Space Complexity

–

Optimal Solution

Approach

The clever approach is to remember the temperatures we've seen and their positions. We go through the list of temperatures once, and if we find a warmer temperature than one we saw earlier, we can figure out how many days we had to wait.

Here's how the algorithm would work step-by-step:

Go through the temperatures one by one.
For each temperature, check if there are any earlier days we are still 'waiting' for because they had lower temperatures.
If you find an earlier day with a lower temperature and today's temperature is higher, calculate the number of days you waited and record it for that earlier day.
Keep doing this until you've either found all the days that needed to be updated or you run out of 'waiting' days.
Add the current temperature and its position to our 'waiting' list in case later temperatures need it.
After going through all the temperatures, any days left in the 'waiting' list didn't have a warmer day, so mark them with zero.

Code Implementation

def daily_temperatures(temperatures):
    number_of_days = len(temperatures)
    result = [0] * number_of_days
    waiting_days = []

    for current_day, current_temperature in enumerate(temperatures):
        # Check for warmer days for past temperatures.
        while waiting_days and current_temperature > waiting_days[-1][0]:
            past_temperature, past_day = waiting_days.pop()
            result[past_day] = current_day - past_day

        # Store current temperature and index for future comparison.
        waiting_days.append((current_temperature, current_day))

    # Remaining days in stack don't have warmer days.
    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the temperatures array of size n once. Inside the outer loop, there is a while loop that processes the stack of waiting days. Each day can only be added and removed from the stack once. Thus, the inner while loop runs at most n times across the entire algorithm, not for each of the n iterations of the outer loop. Therefore, the time complexity is dominated by the single pass through the input array, resulting in O(n) time complexity.

Space Complexity

O(N) – The solution uses a 'waiting' list to store temperatures and their positions. In the worst-case scenario, where the temperatures are monotonically decreasing, all N temperatures will be added to the 'waiting' list before a warmer temperature is encountered. This means the auxiliary space used by the 'waiting' list grows linearly with the input size N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an exception (depending on requirements and language conventions) to avoid null pointer exceptions or undefined behavior.
Input array with only one element	Return an array of size one with a value of 0, as there are no future days to compare to.
Input array where temperatures are always decreasing	Return an array filled with 0s, as no warmer day will be found for any day.
Input array where temperatures are always increasing	The stack will only contain one element at a time, and the algorithm will efficiently compute waiting days.
Large input array to test for time complexity	The stack-based approach should provide O(n) time complexity, which scales linearly with the size of the input.
Input array with identical temperatures	The result array will be filled with zeros as no warmer temperature exists for any day.
Temperatures reach the maximum or minimum integer values	The comparison logic will work correctly as long as no arithmetic operations cause integer overflow/underflow, which should be avoided within the solution.
Input array with negative temperature values	The comparison logic should still work correctly as the problem states relative comparison not specific temperature ranges are important.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of temperature values in the input array?
What is the maximum possible length of the `temperatures` array?
If a warmer temperature never occurs after a given day, should the corresponding element in the result array be 0?
Is the input array guaranteed to be non-empty?
Can I assume the input will always be valid, or should I handle potential null or invalid inputs?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For each day on the list, we will start looking at all the days that come after it.
We will compare the temperature of the current day with the temperature of each following day, one by one.
If we find a day that's warmer, we count how many days it took to get there and remember that number.
If we get to the end of the list without finding a warmer day, we know the answer for that day is zero.
We repeat this process, looking at every single day to see when the next warmer day is.

Code Implementation

def daily_temperatures_brute_force(temperatures):
    number_of_days = len(temperatures)
    days_to_warmer = [0] * number_of_days

    for current_day in range(number_of_days):
        # Iterate through each day to find warmer temperature.

        for future_day in range(current_day + 1, number_of_days):
            # Compare current day's temp with each subsequent day.
            if temperatures[future_day] > temperatures[current_day]:
                days_to_warmer[current_day] = future_day - current_day
                break

        # If no warmer day is found, the default value remains 0

    return days_to_warmer

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

–

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the temperatures one by one.
For each temperature, check if there are any earlier days we are still 'waiting' for because they had lower temperatures.
If you find an earlier day with a lower temperature and today's temperature is higher, calculate the number of days you waited and record it for that earlier day.
Keep doing this until you've either found all the days that needed to be updated or you run out of 'waiting' days.
Add the current temperature and its position to our 'waiting' list in case later temperatures need it.
After going through all the temperatures, any days left in the 'waiting' list didn't have a warmer day, so mark them with zero.

Code Implementation

def daily_temperatures(temperatures):
    number_of_days = len(temperatures)
    result = [0] * number_of_days
    waiting_days = []

    for current_day, current_temperature in enumerate(temperatures):
        # Check for warmer days for past temperatures.
        while waiting_days and current_temperature > waiting_days[-1][0]:
            past_temperature, past_day = waiting_days.pop()
            result[past_day] = current_day - past_day

        # Store current temperature and index for future comparison.
        waiting_days.append((current_temperature, current_day))

    # Remaining days in stack don't have warmer days.
    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an exception (depending on requirements and language conventions) to avoid null pointer exceptions or undefined behavior.
Input array with only one element	Return an array of size one with a value of 0, as there are no future days to compare to.
Input array where temperatures are always decreasing	Return an array filled with 0s, as no warmer day will be found for any day.
Input array where temperatures are always increasing	The stack will only contain one element at a time, and the algorithm will efficiently compute waiting days.
Large input array to test for time complexity	The stack-based approach should provide O(n) time complexity, which scales linearly with the size of the input.
Input array with identical temperatures	The result array will be filled with zeros as no warmer temperature exists for any day.
Temperatures reach the maximum or minimum integer values	The comparison logic will work correctly as long as no arithmetic operations cause integer overflow/underflow, which should be avoided within the solution.
Input array with negative temperature values	The comparison logic should still work correctly as the problem states relative comparison not specific temperature ranges are important.