MediumStack & Queue
Daily Temperatures
Days until warmer temperature
Solution Approach
Monotonic stack to track indices. Pop when warmer temp found and calculate days difference.
Implementation
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = []
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_idx = stack.pop()
result[prev_idx] = i - prev_idx
stack.append(i)
return resultComplexity Analysis
Time Complexity
O(n)Space Complexity
O(n)Complexity
Time:O(n)
Space:O(n)
Asked at
GoogleAmazonFacebook