We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Daily Temperatures

Number: 739

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Bloomberg, Microsoft, Agoda, TikTok, Anduril, Intuit, Zoho, Swiggy, Meta, ServiceNow, Oracle, Visa, Walmart Labs, Okta, Accenture, Apple, Netflix, Adobe, Tinkoff, Yahoo, Flipkart, Salesforce, PhonePe, SAP

Problem Description

Given an array of integers representing daily temperatures, return an array where for each day you provide the number of days until a warmer temperature occurs. If no such warmer day exists in the future, the answer for that day is 0.

Key Insights

  • Use a monotonic stack to keep track of indices of days with unresolved warmer temperatures.
  • As you iterate through the temperatures, resolve previous days that have found a warmer temperature.
  • The index differences yield the number of days waited until a warmer temperature.

Space and Time Complexity

Time Complexity: O(n), where n is the number of temperatures, because each index is pushed and popped from the stack at most once. Space Complexity: O(n) for storing the stack and the answer array.

Solution

The solution uses a monotonic stack to track the indices whose next warmer temperature has not been found yet. As you iterate through the temperature list, compare the current temperature with the temperature at the index stored at the top of the stack. If the current temperature is higher, it means you've found a warmer day for the day represented by the index from the stack. Pop that index, calculate the difference between the current index and the popped index, and store the result. Push the current index onto the stack for future comparisons. This approach efficiently finds the answer without nested iterations.

Code Solutions

def dailyTemperatures(temperatures):
    n = len(temperatures)
    # Initialize answer list with zeros
    answer = [0] * n
    # Stack to keep indices of temperatures with unresolved next warmer days
    stack = []
    # Iterate through the temperature list
    for i, temp in enumerate(temperatures):
        # Check if the current temperature resolves any previous indices
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()  # Get the index of the previous colder day
            answer[prev_index] = i - prev_index  # Update the number of days waited
        # Push the current index onto the stack
        stack.append(i)
    return answer

# Example usage:
if __name__ == "__main__":
    temps = [73,74,75,71,69,72,76,73]
    print(dailyTemperatures(temps))
← Back to All Questions