Daily Temperatures

You are given an array of integers temperatures where temperatures[i] represents the daily temperature on the ith day.

Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears. If there is no future day with a warmer temperature, set result[i] = 0.

Examples

• 1 ≤ temperatures.length ≤ 1000
• 1 ≤ temperatures[i] ≤ 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• Monotonic Stack — a stack that maintains elements in increasing or decreasing order to efficiently find the next greater element
• Array Traversal — iterating through arrays both forward and backward to compute results
• Dynamic Programming (Basic) — reusing previously computed results to skip unnecessary comparisons

1. Brute Force

Intuition

For each day, we look forward through every future day until we find one with a strictly higher temperature. If we find one, we record the number of days waited. If we reach the end without finding one, we record 0.

This is straightforward but slow — in the worst case (strictly decreasing temperatures), every element scans all remaining elements, giving O(n²) time.

Algorithm

• For each index i, start a pointer j = i + 1.
• Advance j while temperatures[j] ≤ temperatures[i].
• If j reaches n, record 0. Otherwise record j − i.
• Return the result array.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = []

        for i in range(n):
            count = 1
            j = i + 1
            while j < n:
                if temperatures[j] > temperatures[i]:
                    break
                j += 1
                count += 1
            count = 0 if j == n else count
            res.append(count)
        return res

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    res[i] = j - i;
                    break;
                }
            }
        }
        return res;
    }
}

Time Complexity: O(n²)
Space Complexity: O(1) extra space, O(n) for the output array.

2. Monotonic Stack

Intuition

The brute force scans forward repeatedly because it doesn't remember which days are still waiting for a warmer temperature. A stack fixes this: we keep a “waiting list” of days (stored as (temperature, index)pairs) that haven't yet found their warmer future day.

As we scan left to right, whenever the current temperature is strictly greater than the top of the stack, we've just found the answer for that waiting day. We pop it, compute i − stackInd, and store the result. We keep popping as long as the condition holds. Then we push the current day onto the stack.

The stack stays in monotonically decreasing order of temperature — each element on the stack is colder than all elements below it. Any day that gets pushed will eventually be popped when a warmer day arrives, or it will remain (meaning its answer is 0). Because every element is pushed and popped at most once, the total work is O(n).

Algorithm

• Initialize res = [0] * n and an empty stack.
• For each (i, t) in the temperatures array:
• While the stack is non-empty and t > stack[-1][0] (current temp warmer than stack top): pop the top, compute res[stackInd] = i − stackInd.
• Push (t, i) onto the stack.
• Any indices still on the stack at the end have no warmer future day — their res value stays 0.
• Return res.

3. Dynamic Programming

Intuition

Instead of scanning all future days from scratch for each index, we can reuse previously computed answers. If day j is not warmer than day i, we don't need to check j+1 next — we can jump directly to the day that was warmer than j (which is j + res[j]), since if that day wasn't warmer than j it can't be warmer than i either (because temps[i] ≥ temps[j]).

By traversing right-to-left and using previously filled res values as jump pointers, we avoid redundant comparisons. Each element is still visited multiple times in theory, but in practice the jumps skip large sections.

Algorithm

• Initialize res = [0] * n.
• Traverse from right to left: i = n-2 down to 0.
• Start j = i + 1.
• While j < n and temperatures[j] ≤ temperatures[i]:
• If res[j] == 0: no warmer day exists beyond j, break.
• Otherwise: jump j += res[j].
• If j < n and temperatures[j] > temperatures[i]: set res[i] = j − i.
• Return res.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = [0] * n

        for i in range(n - 2, -1, -1):
            j = i + 1
            while j < n and temperatures[j] <= temperatures[i]:
                if res[j] == 0:
                    j = n
                    break
                j += res[j]

            if j < n:
                res[i] = j - i
        return res

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        for (int i = n - 2; i >= 0; i--) {
            int j = i + 1;
            while (j < n && temperatures[j] <= temperatures[i]) {
                if (res[j] == 0) { j = n; break; }
                j += res[j];
            }
            if (j < n) res[i] = j - i;
        }
        return res;
    }
}

Time Complexity: O(n) amortized
Space Complexity: O(1) extra space, O(n) for the output array.

Common Pitfalls

Using Greater-Than-or-Equal Instead of Strictly Greater

The problem asks for a warmer day — strictly greater temperature. Using >= instead of > causes the algorithm to pop stack entries when temperatures are equal, which is wrong. Two days with the same temperature do not count as one being warmer than the other.

# Wrong: pops on equal temperatures
while stack and t >= stack[-1][0]:
    stackT, stackInd = stack.pop()

# Correct: strictly warmer only
while stack and t > stack[-1][0]:
    stackT, stackInd = stack.pop()
    res[stackInd] = i - stackInd

Storing Only Indices Without Tracking Temperature

When the stack stores only indices (not the (temperature, index) pair), you still need to look up the temperature via temperatures[stack[-1]] during comparison. A common mistake is comparing the index value itself against the current temperature, which produces nonsensical results.

# If storing only indices, access temperature via the array
stack = []  # stores indices
for i, t in enumerate(temperatures):
    while stack and t > temperatures[stack[-1]]:  # lookup via array
        idx = stack.pop()
        res[idx] = i - idx
    stack.append(i)

Off-by-One in Day Counting

The result should be the number of days to wait, which equals the difference in indices i − stackInd. Starting the brute-force counter at count = 0 with j = i + 1 and incrementing after the comparison leads to count being j − i − 1 — one short of the correct answer. Using direct index subtraction j − i avoids this entirely.