algoadvance

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Clarifying Questions:

  1. Can the temperatures be negative?
    • No, temperatures are positive integers.
  2. Is the input list always valid and not empty?
    • Yes, you can assume the input list is always non-empty.
  3. Are the temperatures always integers?
    • Yes, the temperatures are always integers.

Strategy:

  1. Brute Force Approach:
    • For each day, iterate over the subsequent days to find the next warmer day.
    • This approach will work but is not optimal due to its O(n^2) time complexity.
  2. Optimal Approach Using Stack:
    • Utilize a stack to improve the efficiency.
    • The idea is to maintain a stack that helps track the indices of the days with decreasing temperatures.
    • Iterate through the list. For each temperature, check if it is warmer than the temperature at the index stored at the top of the stack.
    • If it is, that means we have found the next warmer day for the indices stored in the stack. Pop the index from the stack and record the difference between the current index and the popped index in the result list.
    • Push the current day index onto the stack.

Code:

from typing import List

def dailyTemperatures(T: List[int]) -> List[int]:
    n = len(T)
    answer = [0] * n
    stack = []
    
    for i in range(n):
        while stack and T[i] > T[stack[-1]]:
            idx = stack.pop()
            answer[idx] = i - idx
        stack.append(i)
    
    return answer

# Example usage:
T = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(T))  # Output: [1, 1, 4, 2, 1, 1, 0, 0]

Time Complexity:

This solution efficiently solves the problem by keeping the time complexity linear, making it suitable for large input sizes.

Try our interview co-pilot at AlgoAdvance.com