Daily Temperatures

Medium

Google

3 views

Topics:

ArraysStacks

You are given an array of integers called temperatures, where each element represents the daily temperature. Your task is to return a new array called answer where answer[i] indicates the number of days you have to wait after the i-th day to encounter a warmer temperature. If there is no future day with a warmer temperature, answer[i] should be 0.

Here's a breakdown of the requirements:

Input: An integer array temperatures representing daily temperatures.
Output: An integer array answer where answer[i] is the number of days to wait for a warmer temperature after day i.
Warmer Temperature: A warmer temperature means a temperature strictly greater than the current day's temperature.
No Warmer Day: If no warmer temperature exists in the future, set answer[i] to 0.

Let's consider a few examples:

Example 1:
- temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
- answer = [1, 1, 4, 2, 1, 1, 0, 0]
Example 2:
- temperatures = [30, 40, 50, 60]
- answer = [1, 1, 1, 0]
Example 3:
- temperatures = [30, 60, 90]
- answer = [1, 1, 0]

Can you provide an efficient algorithm to solve this problem, considering the time and space complexity?

Daily Temperatures

Medium

Google

3 views

Topics:

ArraysStacks

You are given an array of integers called temperatures, where each element represents the daily temperature. Your task is to return a new array called answer where answer[i] indicates the number of days you have to wait after the i-th day to encounter a warmer temperature. If there is no future day with a warmer temperature, answer[i] should be 0.

Here's a breakdown of the requirements:

Input: An integer array temperatures representing daily temperatures.
Output: An integer array answer where answer[i] is the number of days to wait for a warmer temperature after day i.
Warmer Temperature: A warmer temperature means a temperature strictly greater than the current day's temperature.
No Warmer Day: If no warmer temperature exists in the future, set answer[i] to 0.

Let's consider a few examples:

Example 1:
- temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
- answer = [1, 1, 4, 2, 1, 1, 0, 0]
Example 2:
- temperatures = [30, 40, 50, 60]
- answer = [1, 1, 1, 0]
Example 3:
- temperatures = [30, 60, 90]
- answer = [1, 1, 0]

Can you provide an efficient algorithm to solve this problem, considering the time and space complexity?

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 `temperatures` array? Can I assume a reasonable upper bound?
What should I return for a given day if there is no warmer day in the future?
Can the input array `temperatures` be empty or null? If so, what should I return?
Are the temperatures guaranteed to be integers, or could they be floating-point numbers?
What is the maximum size of the `temperatures` array? This will help me think about space and time complexity.

Brute Force Solution

Approach

The brute force approach finds the next warmer day for each day by simply looking at all the following days. It checks each day until a warmer temperature is found, one at a time. If no warmer day exists, it records that as zero.

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

For each day's temperature, start looking at the very next day's temperature.
Compare the current day's temperature to the next day's temperature. If the next day is warmer, record how many days ahead that warmer day is and move to the next day's temperature to check.
If the next day is not warmer, check the day after that. Continue comparing until you find a warmer day.
If you reach the end of the list of temperatures without finding a warmer day, record zero for that day.
Repeat this process for every day in the original list of temperatures.

Code Implementation

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

    for current_day in range(number_of_days):
        # For each day, find the next warmer day
        for future_day in range(current_day + 1, number_of_days):
            # Check for a warmer day
            if temperatures[future_day] > temperatures[current_day]:
                days_until_warmer[current_day] = future_day - current_day

                # Exit once a warmer day is found
                break

    # Return the result
    return days_until_warmer

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input temperature list, which has a size of n. For each temperature, the algorithm potentially iterates through the rest of the temperature list to find the next warmer day. In the worst-case scenario, for each of the n days, it might need to compare against close to n days to find a warmer temperature. Thus, the number of operations grows proportionally to n multiplied by n, leading to a time complexity of O(n²).

Space Complexity

O(1) – The brute force approach iterates through the input array of temperatures but doesn't create any auxiliary data structures that scale with the input size. The algorithm only uses a few variables, such as loop counters or indices to track the current and next days being compared. The space required for these variables remains constant regardless of the number of days (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

We want to find, for each day, how many days we need to wait until a warmer temperature appears. Instead of checking every future day for each day, we'll use a helpful tool to keep track of promising future days, which will reduce redundant comparisons and improve efficiency.

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

Imagine you have a special notebook to write down days where you've seen a certain temperature, but only if that temperature is worth remembering.
Go through the temperatures one by one, from the start.
For each day's temperature, check your notebook. If there are days listed with lower temperatures than the current day, you've found how long those earlier days had to wait for a warmer day! Calculate the difference and update the answer for those earlier days.
Remove those earlier days from the notebook since you've found their answer and they're no longer needed.
If the current day's temperature is not in your notebook, or it's higher than everything currently there, then add the current day and its temperature to the notebook. It might be useful later.
Repeat until you've gone through all the temperatures.

Code Implementation

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

    for current_day_index, current_temperature in enumerate(temperatures):
        #Find warmer days for previous indices.
        while temperature_stack and current_temperature > temperature_stack[-1][0]:

            previous_temperature, previous_day_index = temperature_stack.pop()

            days_to_wait[previous_day_index] = current_day_index - previous_day_index

        # Store the current day and temperature
        temperature_stack.append((current_temperature, current_day_index))

    return days_to_wait

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the n temperatures once. Inside the loop, there's a while loop that processes elements in a stack. Each element is pushed onto the stack once and popped at most once. Therefore, the operations within the while loop, in aggregate across all iterations of the outer loop, are bounded by O(n). The outer loop is O(n) and the inner while loop is O(n) amortized, the overall time complexity is O(n) + O(n) which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses a 'special notebook' (implicitly a stack) to store the days and their corresponding temperatures. In the worst-case scenario, where the temperatures are monotonically decreasing, all N days will be added to the stack before any warmer days are found. Thus, the auxiliary space used by the stack can grow up to N, where N is the number of days. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty array since there are no temperatures to process.
Array with only one element	Return an array containing only 0, as there's no future day to compare with.
Temperatures are monotonically decreasing	All elements in the result array should be 0, as no warmer day exists for any day.
Temperatures are monotonically increasing	The result array will have increasing wait times until the last element, which will be 0.
Large temperature values (close to integer limit)	Ensure no integer overflow occurs during comparison or calculation of wait days.
Array contains all identical temperature values	The output array should consist entirely of zeros, indicating no warmer day found.
Temperatures fluctuating rapidly (many local minima and maxima)	The stack-based approach handles this efficiently by popping elements when a warmer day is found.
Maximum sized input array	Verify that the solution's time and space complexity remains within acceptable bounds for the maximum possible input size.