The Daily Temperatures Problem

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!