Jobs

Interviews

Discussions

Daily Temperatures

Medium

Asked by:

+23

More companies

289 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

Medium

Asked by:

+17

More companies

289 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 (e.g., integers, floats, positive, negative)?
What is the maximum possible size of the `temperatures` array?
Can the input array be empty? If so, what should be returned?
Are the temperatures guaranteed to be unique, or can there be duplicate temperature values on different days?
If no warmer temperature exists for a given day, should the wait be represented by 0 or some other specific value like -1 or `null`?

Brute Force Solution

Approach

For each day's temperature, we want to find out how many days we have to wait until a warmer temperature occurs. The brute force way to do this is to simply check every single day that comes after the current day.

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

Take the first day's temperature.
Look at the very next day's temperature. Is it warmer? If yes, we found our answer for the first day. If no, keep looking.
If the next day wasn't warmer, check the day after that. Is that one warmer? Continue this process, looking at each subsequent day one by one.
Keep track of how many days you had to check before you found a warmer one. If you reach the end without finding a warmer day, that means there isn't one.
Now, do the exact same thing for the second day's temperature: check every day after it until you find a warmer one.
Repeat this entire process for every single day in the list, finding the waiting period for each one.

Code Implementation

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

    # Iterate through each day's temperature to find its waiting period
    for current_day_index in range(number_of_days):
        current_day_temperature = temperatures[current_day_index]
        days_to_wait = 0
        found_warmer_day = False

        # Check subsequent days for a warmer temperature
        for lookahead_day_index in range(current_day_index + 1, number_of_days):
            lookahead_day_temperature = temperatures[lookahead_day_index]
            days_to_wait += 1

            # If a warmer day is found, record the waiting period and stop searching for this day
            if lookahead_day_temperature > current_day_temperature:
                waiting_days_result[current_day_index] = days_to_wait
                found_warmer_day = True
                break

        # If no warmer day was found after checking all subsequent days, the waiting period remains 0
        if not found_warmer_day:
            waiting_days_result[current_day_index] = 0

    return waiting_days_result

Big(O) Analysis

Time Complexity

O(n²) – The described approach involves iterating through each day's temperature. For each day, it then scans through all subsequent days to find the first warmer temperature. If 'n' is the number of days, the outer loop processes 'n' days, and the inner loop, in the worst case, could also scan up to 'n' days for each outer loop iteration. This nested structure, where for each of 'n' elements we perform an operation that could take up to 'n' steps, results in approximately n * n/2 comparisons. Therefore, the total time complexity is quadratic, simplifying to O(n²).

Space Complexity

O(N) – The solution requires an auxiliary array, let's call it 'results', to store the waiting period for each day. This 'results' array will have the same number of elements as the input temperature list, which is N. Therefore, the auxiliary space used is directly proportional to the input size N. The space complexity simplifies to O(N).

Optimal Solution

Approach

We want to find the number of days you need to wait for a warmer temperature. The clever approach uses a special structure to keep track of recent colder days. When a warmer day arrives, it can quickly tell how many days passed since the previously colder days.

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

Imagine you're going through the temperatures day by day.
As you look at each day's temperature, you also keep a mental note of the days you've seen so far that were colder than the current day, and how many days ago they were.
When you encounter a day with a warmer temperature, you immediately know it's the warmer day you were waiting for for all those recent colder days you've noted.
So, for each of those colder days, you record the number of days that passed until this warmer day.
If the current day's temperature isn't warmer than some of the recent colder days you're tracking, you add the current day to your list of colder days to consider for future warmer days.
This way, you're always efficiently matching warmer days to the most recent colder days that came before them.

Code Implementation

def dailyTemperatures(temperatures):
    number_of_days = len(temperatures)
    days_to_wait_result = [0] * number_of_days
    # Stack to store indices of days with temperatures that haven't found a warmer day yet.
    indices_of_colder_days_stack = []

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

        # While there are days in the stack and the current day is warmer than the day at the top of the stack.
        while indices_of_colder_days_stack and current_temperature > temperatures[indices_of_colder_days_stack[-1]]:
            previous_colder_day_index = indices_of_colder_days_stack.pop()
            # Calculate and store the number of days until a warmer day.
            days_to_wait_result[previous_colder_day_index] = current_day_index - previous_colder_day_index

        # Push the current day's index onto the stack if it's not warmer than previous days or if the stack is empty.
        indices_of_colder_days_stack.append(current_day_index)

    return days_to_wait_result

Big(O) Analysis

Time Complexity

O(n) – We iterate through the array of temperatures once. For each temperature, we might perform a constant number of operations on a stack data structure. While the stack can grow up to size n, each element is pushed onto and popped from the stack at most once. Therefore, the total number of operations is proportional to the number of elements in the input array, n. This results in a linear time complexity of O(n).

Space Complexity

O(n) – The solution uses a stack to keep track of the indices of days for which we haven't yet found a warmer day. In the worst-case scenario, if the temperatures are strictly decreasing, all N days' indices might be pushed onto the stack. Therefore, the auxiliary space complexity is directly proportional to the number of days, N, leading to O(n) space.

Edge Cases

Case	How to Handle
Empty input array temperatures	An empty input array should result in an empty output array.
Input array with a single element	A single element array should result in an output array with a single zero, as there are no future days.
All temperatures are the same	If all temperatures are identical, the output array should contain all zeros because no warmer day will ever occur.
Temperatures are strictly decreasing	If temperatures are strictly decreasing, no warmer day exists for any given day, so the output array should be all zeros.
Temperatures are strictly increasing	If temperatures are strictly increasing, the wait for each day will be exactly 1.
Temperatures contain negative values or zero	The algorithm should handle negative temperatures and zero correctly as numerical comparisons remain valid.
Extremely large input array	The chosen stack-based approach offers O(n) time complexity, making it efficient for large inputs.
Input array with mixed ascending and descending sequences	The monotonic stack correctly identifies the next warmer day by popping elements that are no longer candidates.

Empty input array temperatures

How to Handle:

An empty input array should result in an empty output array.

Input array with a single element

How to Handle:

A single element array should result in an output array with a single zero, as there are no future days.

All temperatures are the same

How to Handle:

If all temperatures are identical, the output array should contain all zeros because no warmer day will ever occur.

Temperatures are strictly decreasing

How to Handle:

If temperatures are strictly decreasing, no warmer day exists for any given day, so the output array should be all zeros.

Temperatures are strictly increasing

How to Handle:

If temperatures are strictly increasing, the wait for each day will be exactly 1.

Temperatures contain negative values or zero

How to Handle:

The algorithm should handle negative temperatures and zero correctly as numerical comparisons remain valid.

Extremely large input array

How to Handle:

The chosen stack-based approach offers O(n) time complexity, making it efficient for large inputs.

Input array with mixed ascending and descending sequences

How to Handle:

The monotonic stack correctly identifies the next warmer day by popping elements that are no longer candidates.

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 (e.g., integers, floats, positive, negative)?
What is the maximum possible size of the `temperatures` array?
Can the input array be empty? If so, what should be returned?
Are the temperatures guaranteed to be unique, or can there be duplicate temperature values on different days?
If no warmer temperature exists for a given day, should the wait be represented by 0 or some other specific value like -1 or `null`?

Brute Force Solution

Approach

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

Take the first day's temperature.
Look at the very next day's temperature. Is it warmer? If yes, we found our answer for the first day. If no, keep looking.
If the next day wasn't warmer, check the day after that. Is that one warmer? Continue this process, looking at each subsequent day one by one.
Keep track of how many days you had to check before you found a warmer one. If you reach the end without finding a warmer day, that means there isn't one.
Now, do the exact same thing for the second day's temperature: check every day after it until you find a warmer one.
Repeat this entire process for every single day in the list, finding the waiting period for each one.

Code Implementation

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

    # Iterate through each day's temperature to find its waiting period
    for current_day_index in range(number_of_days):
        current_day_temperature = temperatures[current_day_index]
        days_to_wait = 0
        found_warmer_day = False

        # Check subsequent days for a warmer temperature
        for lookahead_day_index in range(current_day_index + 1, number_of_days):
            lookahead_day_temperature = temperatures[lookahead_day_index]
            days_to_wait += 1

            # If a warmer day is found, record the waiting period and stop searching for this day
            if lookahead_day_temperature > current_day_temperature:
                waiting_days_result[current_day_index] = days_to_wait
                found_warmer_day = True
                break

        # If no warmer day was found after checking all subsequent days, the waiting period remains 0
        if not found_warmer_day:
            waiting_days_result[current_day_index] = 0

    return waiting_days_result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you're going through the temperatures day by day.
As you look at each day's temperature, you also keep a mental note of the days you've seen so far that were colder than the current day, and how many days ago they were.
When you encounter a day with a warmer temperature, you immediately know it's the warmer day you were waiting for for all those recent colder days you've noted.
So, for each of those colder days, you record the number of days that passed until this warmer day.
If the current day's temperature isn't warmer than some of the recent colder days you're tracking, you add the current day to your list of colder days to consider for future warmer days.
This way, you're always efficiently matching warmer days to the most recent colder days that came before them.

Code Implementation

def dailyTemperatures(temperatures):
    number_of_days = len(temperatures)
    days_to_wait_result = [0] * number_of_days
    # Stack to store indices of days with temperatures that haven't found a warmer day yet.
    indices_of_colder_days_stack = []

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

        # While there are days in the stack and the current day is warmer than the day at the top of the stack.
        while indices_of_colder_days_stack and current_temperature > temperatures[indices_of_colder_days_stack[-1]]:
            previous_colder_day_index = indices_of_colder_days_stack.pop()
            # Calculate and store the number of days until a warmer day.
            days_to_wait_result[previous_colder_day_index] = current_day_index - previous_colder_day_index

        # Push the current day's index onto the stack if it's not warmer than previous days or if the stack is empty.
        indices_of_colder_days_stack.append(current_day_index)

    return days_to_wait_result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array temperatures	An empty input array should result in an empty output array.
Input array with a single element	A single element array should result in an output array with a single zero, as there are no future days.
All temperatures are the same	If all temperatures are identical, the output array should contain all zeros because no warmer day will ever occur.
Temperatures are strictly decreasing	If temperatures are strictly decreasing, no warmer day exists for any given day, so the output array should be all zeros.
Temperatures are strictly increasing	If temperatures are strictly increasing, the wait for each day will be exactly 1.
Temperatures contain negative values or zero	The algorithm should handle negative temperatures and zero correctly as numerical comparisons remain valid.
Extremely large input array	The chosen stack-based approach offers O(n) time complexity, making it efficient for large inputs.
Input array with mixed ascending and descending sequences	The monotonic stack correctly identifies the next warmer day by popping elements that are no longer candidates.

Empty input array temperatures

How to Handle:

An empty input array should result in an empty output array.

Input array with a single element

How to Handle:

A single element array should result in an output array with a single zero, as there are no future days.

All temperatures are the same

How to Handle:

If all temperatures are identical, the output array should contain all zeros because no warmer day will ever occur.

Temperatures are strictly decreasing

How to Handle:

If temperatures are strictly decreasing, no warmer day exists for any given day, so the output array should be all zeros.

Temperatures are strictly increasing

How to Handle:

If temperatures are strictly increasing, the wait for each day will be exactly 1.

Temperatures contain negative values or zero

How to Handle:

The algorithm should handle negative temperatures and zero correctly as numerical comparisons remain valid.

Extremely large input array

How to Handle:

The chosen stack-based approach offers O(n) time complexity, making it efficient for large inputs.

Input array with mixed ascending and descending sequences

How to Handle:

The monotonic stack correctly identifies the next warmer day by popping elements that are no longer candidates.