Daily Temperatures

Approach Summary

Monotonic decreasing stack of indices. When current temp > stack top temp, pop and record the wait time.

Full Solution & Approach

For each day you want the next warmer day — the classic next-greater-element problem with distances instead of values. A monotonic decreasing stack of indices does it in one pass. Iterate through the array; while the stack is non-empty and the current temperature is warmer than the temperature at the index on top of the stack, the current day is the answer for that top index — pop it and record the difference. Then push the current index. The stack stays strictly decreasing in temperature from bottom to top, which guarantees that when a warmer day arrives it correctly resolves every index it can. Each index is pushed once and popped once, so the total work is linear. The monotonic-stack pattern — a stack that pops when the invariant breaks — is the same machinery behind largest-rectangle and next-greater-element, and recognizing it turns O(n²) "scan right for each element" into O(n).

Each index enters and leaves the stack exactly once — O(n) time. The stack holds up to n indices — O(n) space.

Solution Code

Solution

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    res = [0] * n
    stack = []
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

function dailyTemperatures(temperatures) {
  const res = new Array(temperatures.length).fill(0);
  const stack = [];
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const j = stack.pop();
      res[j] = i - j;
    }
    stack.push(i);
  }
  return res;
}

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int j = stack.pop();
            res[j] = i - j;
        }
        stack.push(i);
    }
    return res;
}

vector<int> dailyTemperatures(const vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> res(n, 0);
    vector<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && temperatures[i] > temperatures[stk.back()]) {
            int j = stk.back();
            stk.pop_back();
            res[j] = i - j;
        }
        stk.push_back(i);
    }
    return res;
}

Edge Cases to Watch

Monotonically decreasing temperatures — all answers are 0
Monotonically increasing temperatures — every answer is 1
The hottest day — always 0
Equal temperatures — the strict comparison means equal days do not resolve each other

How to Recognize This Pattern

Next greater element with distance
Days until warmer

Complexity Analysis

Time Complexity

O(n)

Space Complexity