Daily Temperatures

Days until a warmer temperature — monotonic decreasing stack of indices, O(n) next-greater-element pattern.

intermediate3 min readUpdated Aug 4, 2026

dsa
stack
interview
Google
Meta

The problem

temperatures[i] is the temp on day i. Return answer[i] = number of days you wait after day i for a strictly warmer day. If none, 0.

temperatures = [73,74,75,71,69,72,76,73]
answer       = [1, 1, 4, 2, 1, 1, 0, 0]

Classic next greater element to the right.

Brute force

function dailyTemperaturesBrute(temperatures: number[]): number[] {
  const n = temperatures.length;
  const ans = new Array<number>(n).fill(0);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (temperatures[j] > temperatures[i]) {
        ans[i] = j - i;
        break;
      }
    }
  }
  return ans;
}


Time	O(n²)
Space	O(1) extra

Optimal: monotonic stack

Keep indices of days with decreasing temperatures (waiting for a warmer day). When today’s temp is warmer than stack top, pop and resolve that day.

function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const ans = new Array<number>(n).fill(0);
  const stack: number[] = []; // indices, temps decreasing

  for (let i = 0; i < n; i++) {
    while (
      stack.length &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const j = stack.pop()!;
      ans[j] = i - j;
    }
    stack.push(i);
  }
  return ans;
}


Time	O(n) each index push/pop once
Space	O(n)

Walk `[73,74,75,71,69,72,76,73]`

73 push
74 > 73 → ans[0]=1, push 74
75 > 74 → ans[1]=1, push 75
71,69 push (cooler)
72 > 69 → ans[4]=1; 72 > 71 → ans[3]=2; push 72
76 clears 72,75 → …
73 push; stack leftovers stay 0

Edge cases

Strictly decreasing → all zeros
Strictly increasing → all ones except last
Plateaus (equal) — stack keeps earlier; equal does not pop (need strictly warmer)
Single day → [0]

Common mistakes

Storing values instead of indices (need distance)
Using >= when problem wants strict >
Nested loops and claiming O(n)

Mental model

Monotonic stack stores unresolved days waiting for a warmer future. Stack temps are decreasing (or non-increasing depending on equality rules). When a warmer day arrives, it resolves a suffix of waiting days in one go.

This pattern generalizes to stock span, next greater element, and histogram rectangles.

Why indices not values

You need j - i distances. Storing only temperatures loses positions. Always push indices for this family of problems.

Out-loud answer

“Next greater element to the right, distances. Monotonic decreasing stack of indices. For each day, pop cooler days and set answers. O(n) because each index pushed and popped once.”

Next greater element I/II
Largest rectangle in histogram
Online stock span

Interview delivery

Next greater to the right.
Brute O(n²).
Monotonic stack of indices.
Trace equals carefully.
O(n).