The Daily Temperatures Problem
Given a list of temperatures denoted as "temps" we will determine how many days we must wait for a warmer day.
The two solutions:-
- A brute-force O(n^2) solution
- An optimized O(n) stack-based solution.
Takeaways:-
- Why optimizing code matters
- Role of efficient problem-solving techniques
Problem Statement
The temperatures in the array are such that temp[i] represents the temperature for the given day i.
For each day, we need to find t the number of days until we encounter a warmer temperature.
If there's no day greater than "today" with a higher temperature, return 0 for that day.
Example One
# Input
arr= [73, 74, 75, 71, 69, 72, 76, 73]
# Output
res = [1, 1, 4, 2, 1, 1, 0, 0]
What do these results mean?
- On day 0 (temp 73°F), we wait 1 day for a warmer day.
- On day 2 (temp 75°F), we wait 4 days for a warmer day.
- On day 6 (temp 76°F), there is no warmer future day, so we return 0.
Brute-Force Solution: (O(n²) Time Complexity)
In the brute-force approach, two loops compare each day's temperature with future days.
from typing import List
class WarmerTemperature:
def max_daily_temps(self, temp: List[int]) -> List[int]:
"""
Brute-Force Warmer Temperature sol
Args:
temp(List): temperatures for given days
Returns:
List[integers]: List of days
"""
sol = []
for i in range(len(temp)):
j = i + 1
count = 1
while j < len(temp):
if temp[j] > temp[i]:
sol.append(count)
break
count += 1
j += 1
else:
sol.append(0)
return sol
Explanation
For each day, we iterate through future days to find the next temperature warmer than the current one.
If a higher temperature is found, we record the number of days.
If there's no higher temperature, we default to 0.
Time Complexity Analysis
Since we compare each day with all future days, the worst-case complexity is O(n²).
This solution works for small inputs but becomes inefficient for large datasets.
Optimized Solution Using a Stack (O(n) Time Complexity)
This approach uses a monotonic decreasing stack to track temperatures efficiently.
Instead of checking every day in the future, we use a stack to keep track of indices where there's no warmer temperature.
from typing import List
class WarmerTemperature:
def max_daily_temps(self, temps: List[int]) -> List[int]:
"""
Get future warmer temperatures in respect to day i
Args:
temps(List): temperatures list
Returns:
List[int]: List of integers representing max days to the warm temp
"""
# Initialize sol array with 0s
sol = [0] * len(temps)
temp_stack = [] # temp_stack stores indices of unresolved days
for i, t in enumerate(temps):
while temp_stack and temps[temp_stack[-1]] < t:
prev_index = temp_stack.pop()
sol[prev_index] = i - prev_index # days waited
temp_stack.append(i) # Stores the current index in the stack
return sol
Explanation
-
Iterate through the temperatures array only once.
- The stack stores indices of temperatures that haven't found a warmer day.
- When we find a warmer day, we pop from the stack and calculate the difference.
Time Complexity Analysis
Pushing and popping each index from the stack happens only once, making this an O(n) solution.
Space complexity is O(n) in the worst case (if temperatures are decreasing).
Why the Optimized Solution is Better
Approach Time Complexity Space Complexity Performance
Brute Force O(n²) O(1) Slow for large n
Optimized Stack O(n) O(n) Much faster and scalable
The optimized stack-based approach is significantly faster and more memory-efficient for larger datasets.
Where to Go From Here?
We can significantly improve algorithm performance by using efficient data structures like stacks. Try applying this approach to monotonic stack problems like the
Next Greater Element or Stock Span Problem.
If you found this helpful, check out more advanced algorithm techniques and optimize your code today!