739. Daily Temperatures

Problem Link

For each day, the goal is to find the next future day with a higher temperature. Instead of using a brute-force approach with two nested loops, we can resolve multiple previously colder days in a single pass by using a stack.

As we iterate through the days, we store the indices of unresolved days in a stack. Before pushing the current day, we check whether it is warmer than the days represented at the top of the stack. While the stack is not empty and the current temperature is higher, we pop those indices and compute how many days they had to wait.

This process maintains the stack in a monotonically decreasing order of temperatures, ensuring that all colder days are processed as soon as a warmer day appears and that no unresolved day is missed.

Pseudocode

• Process the temperature list from left to right while maintaining a stack that stores indices of days whose warmer temperature has not yet been found.
• For the current day \(r\) with temperature \(temp\), while the stack is not empty and the last recorded temperature is less than \(temp\), we've found the next warmer day for that last temperature.
  • Pop the index \(l\) from the stack and set \(result[l] = r - l\), which is the number of days waited.
• After resolving all smaller temperatures, push the current temperature index \(r\) onto the stack.
• Any indices left in the stack do not have a warmer future day, so their result remains 0.

Runtime Complexity

Time: \(O(n)\), since we only iterate temperatures once, and the stack push/pop operation are constant time

Space: \(O(n)\), stack can grow upto size of temperatures

PythonGo

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        result = [0]*len(temperatures)
        stk = []
        for r, temp in enumerate(temperatures):
            while len(stk) != 0 and temperatures[stk[-1]] < temp:
                l = stk.pop()
                result[l] = r-l

            stk.append(r)
        return result

func dailyTemperatures(temperatures []int) []int {
    result := make([]int, len(temperatures))
    var stk []int
    var l int
    for r, temp := range temperatures {
        for len(stk) != 0 && temperatures[stk[len(stk)-1]] < temp {
            l = stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            result[l] = r - l
        }
        stk = append(stk, r)
    }
    return result
}

---