Jobs

Interviews

Discussions

Daily Temperatures

#19 Most AskedMedium

Daily Temperatures #19 Most Asked

Medium

Netflix

15 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

Try coding it in LeetCode

Daily Temperatures

#19 Most AskedMedium

Daily Temperatures #19 Most Asked

Medium

Netflix

15 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

Try coding it in LeetCode

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 possible temperature values? Can they be negative or zero?
What are the constraints on the size of the input list of temperatures? For example, can it be empty?
Are the temperatures integers, or could they be floating-point numbers?
To confirm, for a temperature at index `i`, we're looking for the *first* future day with a warmer temperature, not just any warmer day, correct?
If the input list contains only one temperature, should the output be a list containing a single zero?

Brute Force Solution

Approach

For each day's temperature, we will look at all the following days, one by one, to find the first day that is warmer. This is like a simple but thorough search where we check every single possibility for each day.

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

Pick a day and remember its temperature.
Now, look at the very next day. Is its temperature warmer than the day you picked?
If it is, then you've found your answer for the original day. Count how many days you had to look forward and record that number.
If it's not warmer, move to the next day after that and check its temperature.
Keep checking each future day, one at a time, until you find one that's warmer.
If you get to the end of the list of days and still haven't found a warmer day, it means there isn't one. In this case, just record a zero for the original day.
Repeat this entire process for every single day in the list, starting from the first day and going all the way to the last.

Code Implementation

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

    # Iterate through each day to find a warmer future day for it.

    for current_day_index in range(number_of_days):
        current_day_temperature = temperatures[current_day_index]

        # Search for a warmer temperature in the subsequent days.

        for future_day_index in range(current_day_index + 1, number_of_days):
            future_day_temperature = temperatures[future_day_index]

            # If a warmer day is found, calculate the day difference and stop searching for this current day.

            if future_day_temperature > current_day_temperature:
                days_to_wait = future_day_index - current_day_index
                answer_list[current_day_index] = days_to_wait
                break

    return answer_list

Big(O) Analysis

Time Complexity

O(n²) – Let n be the number of days in the temperature list. The described approach involves an outer loop that iterates through each of the n days. For each day, a nested inner loop scans all subsequent days to find a warmer temperature. In the worst-case scenario (e.g., a decreasing list of temperatures), the inner loop for the first day will run n-1 times, for the second day n-2 times, and so on. This pattern of operations sums up to (n-1) + (n-2) + ... + 1, which is approximately n * (n-1) / 2. Therefore, the time complexity simplifies to O(n²).

Space Complexity

O(N) – The primary auxiliary space used is for the result list, which must store an answer for each of the N input temperatures. This list is created to record the calculated number of days to wait for a warmer temperature, or zero if no such day exists. Therefore, the space required for this output list grows directly in proportion to the number of days, N, in the input temperature list.

Optimal Solution

Approach

The best way to solve this is to go through the days backwards, from the last day to the first. This approach cleverly keeps track of past warmer days, allowing us to quickly find the next warm day for the current day we are looking at without re-scanning everything.

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

Start by looking at the last day in the list. Since there are no future days, the wait is zero.
Now, move to the day right before that (the second to last day).
Compare this day's temperature to the temperature of the day immediately after it.
If the next day is warmer, then the answer is one day of waiting.
If the next day is not warmer, then you need to figure out when that next day got warmer. We already have the answer for that day, so we can 'jump' ahead that many days to find the next potential warm day.
Keep making these 'jumps' using the pre-calculated waiting times until you find a day that's warmer than your current day.
Once you find a warmer day, calculate the number of days between your current day and that warmer day. That's your answer.
If you 'jump' and run out of future days to check, it means there is no warmer day coming up, so the wait is zero.
Repeat this process, moving backwards one day at a time, until you have calculated the wait time for every single day in the list.

Code Implementation

def dailyTemperatures(temperatures):
    number_of_days = len(temperatures)
    days_until_warmer_temperature = [0] * number_of_days

    # Iterate backwards to use previously calculated waiting times for future days.
    for current_day_index in range(number_of_days - 2, -1, -1):
        next_day_index = current_day_index + 1

        # Keep jumping to the next warmer day until a day warmer than the current day is found.
        while next_day_index < number_of_days and temperatures[next_day_index] <= temperatures[current_day_index]:
            # If there's no warmer day for the next day, there won't be one for the current day either.
            if days_until_warmer_temperature[next_day_index] == 0:
                next_day_index = number_of_days
                break
            next_day_index += days_until_warmer_temperature[next_day_index]

        # If a warmer day was found within bounds, calculate the distance.
        if next_day_index < number_of_days:
            days_until_warmer_temperature[current_day_index] = next_day_index - current_day_index

    return days_until_warmer_temperature

Big(O) Analysis

Time Complexity

O(n) – The solution involves a single pass backward through the array of n temperatures. For each temperature, we might enter a 'jumping' loop to find the next warmer day. Although this looks like a nested loop, each day's index is only considered in the inner 'jumping' process once throughout the entire algorithm. This is because we always jump forward to an unvisited index from the perspective of the inner loop. Therefore, every element is processed a constant number of times in total, leading to a linear time complexity of O(n).

Space Complexity

O(N) – The solution requires an auxiliary array to store the waiting days for each of the N input temperatures. This array is explicitly created to hold the results, and its size is directly proportional to the number of days in the input list. Therefore, the additional space required by the algorithm grows linearly with the input size N.

Edge Cases

Case	How to Handle
An empty input list	The function should return an empty list as there are no temperatures to process.
A list with a single temperature	The result list should contain a single zero, as there are no future days to compare against.
Temperatures are in strictly decreasing order (e.g., [75, 74, 73])	The output list should be all zeros since no day is followed by a warmer day.
Temperatures are in strictly increasing order (e.g., [73, 74, 75])	Each element in the output list will be 1, as every day is followed by a warmer day immediately.
All temperatures in the list are identical (e.g., [70, 70, 70])	The output list will consist entirely of zeros because no temperature is ever warmer than a previous one.
Input list contains the maximum number of elements (e.g., 100,000)	A monotonic stack approach with O(N) time complexity is required to avoid a timeout that would occur with a naive O(N^2) solution.
Input contains the minimum and maximum possible temperature values (e.g., 30 and 100)	The solution must correctly handle calculations and comparisons across the full valid range of temperature values.
A list with a single large spike in temperature at the end (e.g., [70, 60, 50, 80])	The monotonic stack correctly pops all previous colder temperatures to find their next warmer day at the final spike.

An empty input list

How to Handle:

The function should return an empty list as there are no temperatures to process.

A list with a single temperature

How to Handle:

The result list should contain a single zero, as there are no future days to compare against.

Temperatures are in strictly decreasing order (e.g., [75, 74, 73])

How to Handle:

The output list should be all zeros since no day is followed by a warmer day.

Temperatures are in strictly increasing order (e.g., [73, 74, 75])

How to Handle:

Each element in the output list will be 1, as every day is followed by a warmer day immediately.

All temperatures in the list are identical (e.g., [70, 70, 70])

How to Handle:

The output list will consist entirely of zeros because no temperature is ever warmer than a previous one.

Input list contains the maximum number of elements (e.g., 100,000)

How to Handle:

A monotonic stack approach with O(N) time complexity is required to avoid a timeout that would occur with a naive O(N^2) solution.

Input contains the minimum and maximum possible temperature values (e.g., 30 and 100)

How to Handle:

The solution must correctly handle calculations and comparisons across the full valid range of temperature values.

A list with a single large spike in temperature at the end (e.g., [70, 60, 50, 80])

How to Handle:

The monotonic stack correctly pops all previous colder temperatures to find their next warmer day at the final spike.

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 possible temperature values? Can they be negative or zero?
What are the constraints on the size of the input list of temperatures? For example, can it be empty?
Are the temperatures integers, or could they be floating-point numbers?
To confirm, for a temperature at index `i`, we're looking for the *first* future day with a warmer temperature, not just any warmer day, correct?
If the input list contains only one temperature, should the output be a list containing a single zero?

Brute Force Solution

Approach

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

Pick a day and remember its temperature.
Now, look at the very next day. Is its temperature warmer than the day you picked?
If it is, then you've found your answer for the original day. Count how many days you had to look forward and record that number.
If it's not warmer, move to the next day after that and check its temperature.
Keep checking each future day, one at a time, until you find one that's warmer.
If you get to the end of the list of days and still haven't found a warmer day, it means there isn't one. In this case, just record a zero for the original day.
Repeat this entire process for every single day in the list, starting from the first day and going all the way to the last.

Code Implementation

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

    # Iterate through each day to find a warmer future day for it.

    for current_day_index in range(number_of_days):
        current_day_temperature = temperatures[current_day_index]

        # Search for a warmer temperature in the subsequent days.

        for future_day_index in range(current_day_index + 1, number_of_days):
            future_day_temperature = temperatures[future_day_index]

            # If a warmer day is found, calculate the day difference and stop searching for this current day.

            if future_day_temperature > current_day_temperature:
                days_to_wait = future_day_index - current_day_index
                answer_list[current_day_index] = days_to_wait
                break

    return answer_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by looking at the last day in the list. Since there are no future days, the wait is zero.
Now, move to the day right before that (the second to last day).
Compare this day's temperature to the temperature of the day immediately after it.
If the next day is warmer, then the answer is one day of waiting.
If the next day is not warmer, then you need to figure out when that next day got warmer. We already have the answer for that day, so we can 'jump' ahead that many days to find the next potential warm day.
Keep making these 'jumps' using the pre-calculated waiting times until you find a day that's warmer than your current day.
Once you find a warmer day, calculate the number of days between your current day and that warmer day. That's your answer.
If you 'jump' and run out of future days to check, it means there is no warmer day coming up, so the wait is zero.
Repeat this process, moving backwards one day at a time, until you have calculated the wait time for every single day in the list.

Code Implementation

def dailyTemperatures(temperatures):
    number_of_days = len(temperatures)
    days_until_warmer_temperature = [0] * number_of_days

    # Iterate backwards to use previously calculated waiting times for future days.
    for current_day_index in range(number_of_days - 2, -1, -1):
        next_day_index = current_day_index + 1

        # Keep jumping to the next warmer day until a day warmer than the current day is found.
        while next_day_index < number_of_days and temperatures[next_day_index] <= temperatures[current_day_index]:
            # If there's no warmer day for the next day, there won't be one for the current day either.
            if days_until_warmer_temperature[next_day_index] == 0:
                next_day_index = number_of_days
                break
            next_day_index += days_until_warmer_temperature[next_day_index]

        # If a warmer day was found within bounds, calculate the distance.
        if next_day_index < number_of_days:
            days_until_warmer_temperature[current_day_index] = next_day_index - current_day_index

    return days_until_warmer_temperature

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
An empty input list	The function should return an empty list as there are no temperatures to process.
A list with a single temperature	The result list should contain a single zero, as there are no future days to compare against.
Temperatures are in strictly decreasing order (e.g., [75, 74, 73])	The output list should be all zeros since no day is followed by a warmer day.
Temperatures are in strictly increasing order (e.g., [73, 74, 75])	Each element in the output list will be 1, as every day is followed by a warmer day immediately.
All temperatures in the list are identical (e.g., [70, 70, 70])	The output list will consist entirely of zeros because no temperature is ever warmer than a previous one.
Input list contains the maximum number of elements (e.g., 100,000)	A monotonic stack approach with O(N) time complexity is required to avoid a timeout that would occur with a naive O(N^2) solution.
Input contains the minimum and maximum possible temperature values (e.g., 30 and 100)	The solution must correctly handle calculations and comparisons across the full valid range of temperature values.
A list with a single large spike in temperature at the end (e.g., [70, 60, 50, 80])	The monotonic stack correctly pops all previous colder temperatures to find their next warmer day at the final spike.

An empty input list

How to Handle:

The function should return an empty list as there are no temperatures to process.

A list with a single temperature

How to Handle:

The result list should contain a single zero, as there are no future days to compare against.

Temperatures are in strictly decreasing order (e.g., [75, 74, 73])

How to Handle:

The output list should be all zeros since no day is followed by a warmer day.

Temperatures are in strictly increasing order (e.g., [73, 74, 75])

How to Handle:

Each element in the output list will be 1, as every day is followed by a warmer day immediately.

All temperatures in the list are identical (e.g., [70, 70, 70])

How to Handle:

The output list will consist entirely of zeros because no temperature is ever warmer than a previous one.

Input list contains the maximum number of elements (e.g., 100,000)

How to Handle:

A monotonic stack approach with O(N) time complexity is required to avoid a timeout that would occur with a naive O(N^2) solution.

Input contains the minimum and maximum possible temperature values (e.g., 30 and 100)

How to Handle:

The solution must correctly handle calculations and comparisons across the full valid range of temperature values.

A list with a single large spike in temperature at the end (e.g., [70, 60, 50, 80])

How to Handle:

The monotonic stack correctly pops all previous colder temperatures to find their next warmer day at the final spike.

0/35 Netflix questions completed

0/35 completed