Problem Breakdown
We are given an array temperatures representing daily temperatures in degrees Celsius. For each day at index i, we need to find the number of days until a warmer temperature occurs (an element strictly greater than T[i]). If no such future day exists, the value should be 0.
Inputs:
- A list of integers
temperatureswith length between 1 and 30,000. - Values range from 30 to 100 (though logic holds for any integer).
Outputs:
- An array of the same length where each element corresponds to the wait time or 0.
Implicit Constraints & Edge Cases:
- Empty Input: Not possible per constraints, but logically handled by loops not executing.
- Strictly Decreasing Sequence: Every day waits forever; output is all zeros. The stack will fill up and never pop until end of loop (except implicitly via initialization).
- Last Element: Always 0 because there are no future days to check.
- Duplicates: If
T[i] == T[j]where , it does not count as warmer; strictly greater is required.
Intuition
A naive brute-force approach would iterate through the array for every day, checking subsequent days until a higher temperature is found or the end of the list is reached. This results in an time complexity. Given , this could lead to operations, which risks Time Limit Exceeded (TLE) on platforms like LeetCode or production systems.
We need a more efficient way to track “pending” days that are waiting for a warmer temperature. This is the classic Next Greater Element problem pattern.
- We can maintain a stack of indices representing days we haven’t found an answer for yet.
- To optimize, this stack should store temperatures in decreasing order (monotonic). If today’s temperature is higher than what sits at the top of our stack, it means today is the warmer day for that index on the stack. We can resolve those pending queries immediately and pop them off.
Approach
- Initialize a result list
resultwith zeros to handle cases where no warmer day exists (default value). Alternatively, we could append/pop into an array of size N initialized to 0s; I will use pre-allocated logic for clarity on indexing. Actually, initializing the stack and building results dynamically is cleaner in Python if we map indices back later or just initializeresultwith zeros. Let’s initializeresult = [0] * len(T). - Initialize an empty list called
stackto store indices of days waiting for a warmer temperature. The temperatures at these indices will be implicitly decreasing (monotonic). - Iterate through the input array using index
i:- While the stack is not empty and the current day’s temperature (
T[i]) is greater than the temperature at the index stored on top of the stack:- We found a warmer day for the pending request in the stack.
- Pop the previous index from the stack (let’s call it
prev_idx). - Calculate wait time:
i - prev_idx. - Store this value in
result[prev_idx].
- Push current index
ionto the stack, as we are now waiting for a future warmer day.
- While the stack is not empty and the current day’s temperature (
- Return the populated result list.
Complexity Analysis
- Time Complexity: . Each element is pushed onto the stack exactly once and popped at most once during the iteration. The while loop condition ensures amortized constant time per element overall.
- Space Complexity: for the
resultarray (which is required output). Additionally, we use an auxiliary stack which can grow up to size in worst-case scenarios (e.g., strictly decreasing temperatures), so total space complexity remains linear relative to input size.
Solution
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n # Initialize with zeros for days that never get warmer
stack = [] # Stack stores indices of temperatures waiting for a warmer day
for i, temp in enumerate(temperatures):
# While current temperature is higher than the one at top of stack:
while stack and temperatures[stack[-1]] < temp:
prev_idx = stack.pop()
result[prev_idx] = i - prev_idx
# Push current index to wait for future warmer day
stack.append(i)
return result
# Example usage (commented out):
# print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
Edge Cases Handled
- Strictly Decreasing Temperatures: The
whileloop never executes. All indices are pushed to the stack and remain there until the end of iteration. Since we initializedresultwith zeros, all entries correctly return 0 without needing explicit checks after the loop. - Single Element Input: Loop runs once for index 0. Stack gets
[0]. No pop occurs. Returns[0], which is correct as no future day exists. - All Increasing Temperatures: The
whilecondition triggers immediately on every step (except potentially the first). Each popped element finds its answer in , resulting in minimal stack depth and optimal performance matching brute force for this specific case but with better worst-case bounds overall.