Daily Temperatures

Problem Summary

• Given a list of temperatures, find how many days it takes for the next greater temperature to come for each temperature

What is Being Asked?

• Find the next greater element to each item and return the diff between indices OR simply after how many steps is the next greater element to the current one

Main Concepts Used

• Monotonic Stack

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through each item once
• Space: $O(n)$ → Reason: Storing each item once in the stack

Code

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        result = [0] * len(temperatures)
        stack = []
        for i, temp in enumerate(temperatures):
            while stack and stack[-1][1] < temp:
                index, _ = stack.pop()
                result[index] = i - index
            stack.append((i, temp))
        return result