Daily Temperatures

How it works

Instead of checking every future day one by one, we can reuse previously computed answers.
If day j is not warmer than day i, we don’t need to move forward step-by-step — we can simply jump ahead by using the result already stored for day j.
This lets us skip many unnecessary comparisons.
By working backward and using these jumps, we efficiently find the next warmer day for each position.

Steps

1. Create a result list filled with zeros.
2. Traverse the temperature list from right to left.
3. For each day i:
   • Start with the next day j = i + 1.
   • While j is within bounds and not warmer:
     • If res[j] is 0, there is no warmer day ahead → stop.
     • Otherwise, jump forward by res[j] days.
   • If j is within bounds and warmer, set res[i] to j - i.
4. Return res.

Complexity

• Time complexity: O(n)
• Space complexity:
  • O(1) extra space.
  • O(n) space for the output array.

Things to watch for

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

The problem asks for the next warmer day, meaning strictly greater temperature. Using >= instead of > causes the algorithm to stop at equal temperatures, producing incorrect results.

Storing Only Indices Without Temperature Access

When using a stack, you need to compare temperatures. Storing only indices works if you can access temperatures[index], but mixing up index and value access leads to comparison errors.

Off-by-One Errors in Day Counting

The result should be the number of days to wait, which is the difference in indices. Initializing count wrong or miscalculating the difference leads to off-by-one errors.

from typing import List

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:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);

        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;
    }
};