LeetCode 739: Daily Temperatures

Brute force

For each day we can scan into the future and pick the first day with a higher temperature. Time: $\mathcal{O}(n^2)$ .

Stack

If the temperatures are sorted in non-increasing order, no days will have a warmer day in the future. So, if any day has a future warmer day, there must be two consecutive days where temperature increases. Say, $i$ -th is the leftmost day where $t_i < t_{i+1}$ . We can then use $(i+1)$ -th day as the solution for $i$ -th day. Since, $0, 1, 2, \ldots, i$ have non-increasing temperatures, the $i$ -th day cannot be warmer day for any of $0, 1, 2, \ldots, (i-1)$ -th day. Removing $i$ -th day, we now have a smaller problem involving the days: $0, 1, 2, \ldots, (i-1), (i+1), \ldots, (n-1)$ .

In this smaller problem, the leftmost increasing pair is either $t_{i-1} < t_{i+1}$ or it lies in the range $[(i+1) \ldots (n-1)]$ . If $t_{i-1} < t_{i+1}$ , we have again solved $(i-1)$ -th day and have an even smaller problem to solve. Otherwise, the warmer days all are in the range $(i+2), (i+3), \ldots, (n-1)$ . Note, while we are considering $t_{i+1}$ as a potential warmer day, we always look at the unsolved day immediately to its left. So, we use a stack.

Nesting

Another way to think is, say for the $i$ -th day, the earliest warmer day is the $j$ -th day. Then the solutions between these two days are nested like below examples:

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(\texttt{output-size})$

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        waits = [0] * n
        stack = []
        for i, curr_temp in enumerate(temperatures):
            while stack and curr_temp > temperatures[top := stack[-1]]:
                waits[top] = i - top
                stack.pop()
            stack.append(i)

        return waits

unreasonably effective