Daily Temperatures

For each day, walk forward through every later day until one is strictly warmer, and record the distance. If none is found, the answer for that day stays 0.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        answer = [0] * n
        for i in range(n):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    answer[i] = j - i
                    break
        return answer

Correct, but for a long stretch of strictly decreasing temperatures (e.g. [100, 99, 98, ..., 1]), every day has to scan almost the entire rest of the array before giving up — O(n) work per day, O(n²) overall.

The wasted work above comes from re-scanning days we already know don’t have an answer yet. Instead, keep a stack of indices whose warmer day hasn’t been found. The stack is kept monotonically decreasing in temperature (bottom to top): as long as that invariant holds, we never need to look past the top.

When the current day’s temperature is warmer than the temperature at the index on top of the stack, that day is exactly the answer for everything the top (and anything else below it that also qualifies) was waiting for — pop it, record the day-gap, and repeat until the stack top is no longer beaten. Then push the current index, since it now needs its own future warmer day.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = []  # indices of days waiting for a warmer day, decreasing temps
        for i, temp in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < temp:
                j = stack.pop()
                answer[j] = i - j
            stack.append(i)
        return answer

Watch the stack as a waiting room: each day is pushed, and only a warmer day can pop it — at which moment its answer is written as the day gap. Cells marked as answered never need to be looked at again.

Final answer: [1,1,4,2,1,1,0,0], matching the expected output. Each index is pushed exactly once and popped at most once, so the total work across the whole scan is O(n) despite the nested-looking while loop — this is the standard amortized analysis for a monotonic stack. Space is O(n) for the stack in the worst case (e.g. strictly increasing temperatures never push anything that lingers, but strictly decreasing temperatures keep everything on the stack).