Stack crash course ↗ · 20

739. Daily Temperatures

For each day, find how many days you must wait for a warmer temperature. A monotonic decreasing stack of indices lets each element be pushed once and popped once — solving all queries in a single linear pass.

● MediumMonotonic StackNext Greater ElementTypeScript

PROBLEM What we're solving

Given an array temperatures, return an array answer where answer[i] is the number of days after day i until a warmer temperature occurs. If no warmer day exists, answer[i] = 0.

Example: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Day 0 (73°) waits 1 day for day 1 (74°). Day 2 (75°) waits 4 days for day 6 (76°). Days 6 and 7 never find a warmer day — they stay 0.

KEY IDEA Keep a stack of "still waiting" days

Insight → maintain a stack of indices whose answer has not yet been recorded — in order of decreasing temperature. When you reach a new day that is warmer than the top of the stack, you have found the answer for that waiting day: pop it and record i − idx. Push the current index and keep going. Because temperatures can only resolve a waiting day when they are strictly greater, the stack stays monotone decreasing automatically.

RECIPE Scan, pop resolved indices, push current

  • 0 · Initialize. Fill answer with zeros (indices that never resolve stay zero). Prepare an empty stack of number[] to hold indices (not temperatures).
  • 1 · Enter each day. For each index i, check whether the current temperature is strictly greater than the temperature at the index on top of the stack.
  • 2 · Pop and record. While the stack is non-empty and temperatures[i] > temperatures[stack.top], pop idx and set answer[idx] = i − idx. Repeat — one warmer day can resolve many waiting days.
  • 3 · Push. After the while-loop, push i onto the stack. It is now the newest "still waiting" day.
  • 4 · Return. Any index still on the stack never found a warmer day — their zero already sits in answer.
Classic confusion → the stack stores indices, not temperatures. A common mistake is pushing the temperature value itself, then losing the ability to compute i − idx (the gap). Always push the index; look up the temperature via temperatures[stack.top].

COST Complexity & alternatives

Brute force (nested loops)
O(n²)
For each day, scan forward until warmer.
Monotonic stack
O(n)
Each index pushed and popped at most once.

Space is O(n) for the stack in the worst case (a monotone-decreasing input like [100,90,80,…] pushes every index before ever popping). The output array is separate and required by the problem.

Pattern transfer → the same monotonic-stack skeleton solves Next Greater Element I & II (LC 496, 503), Largest Rectangle in Histogram (LC 84), Trapping Rain Water (LC 42), and Online Stock Span(LC 901). Whenever a problem asks "for each element, find the next/prev element that is greater/smaller," reach for a monotonic stack.

RUN IT Monotonic decreasing stack — pop on warmer day

step 0 / 29
STARTInput: 73, 74, 75, 71, 69, 72, 76, 73. Stack is empty; answer is all zeros. We'll scan left to right, pushing indices and popping when a warmer day is found.
1function dailyTemperatures(temperatures: number[]): number[] {
2▶  const n = temperatures.length;
3▶  const answer = new Array<number>(n).fill(0);
4▶  const stack: number[] = [];          // indices, decreasing by temp
5 
6  for (let i = 0; i < n; i++) {
7    // While the current day is warmer than the day at the top of the stack,
8    // that day's wait is finally over — record the gap.
9    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
10      const idx = stack.pop()!;
11      answer[idx] = i - idx;
12    }
13    stack.push(i);                     // push current index, wait for something warmer
14  }
15 
16  // Any index still in the stack never found a warmer day → answer stays 0.
17  return answer;
18}
73
0
74
1
75
2
71
3
69
4
72
5
76
6
73
7
i
—
stack
empty
answer
?
?
?
?
?
?
?
?
current daywaiting on stackbeing popped (resolved)answer recorded
slowfast

TYPESCRIPT The solution, annotated

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

  for (let i = 0; i < n; i++) {
    // While the current day is warmer than the day at the top of the stack,
    // that day's wait is finally over — record the gap.
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const idx = stack.pop()!;
      answer[idx] = i - idx;
    }
    stack.push(i);                     // push current index, wait for something warmer
  }

  // Any index still in the stack never found a warmer day → answer stays 0.
  return answer;
}

Reading it block by block

Lines 3–4 — set up. answerpre-filled with zeros handles the "never warmer" case for free. stack holds indices of days that are still waiting for a warmer successor; it will stay monotone decreasing by temperature.
Lines 7–11 — pop resolved days. The while loop is the heart. For every day i, we keep popping the top index as long as temperatures[i] beats it. The gap i - idx is the number of days waited. One warmer day can resolve many queued days at once.
Line 13 — push. After the while-loop drains all weaker predecessors, index i goes onto the stack as the latest unresolved day. If temperatures[i] is already colder than everything on the stack the while never fires and we just push.
Lines 17–18 — return. Indices still on the stack have answer[idx] = 0 from initialization — no extra pass needed. The amortized cost is O(n): each of the n indices is pushed exactly once and popped at most once.
Complexity → O(n) time amortized — the inner while looks like it could be O(n) per iteration, but each index is pushed exactly once and popped at most once across the entire loop, so the total work across all iterations is O(n). Space is O(n) for the stack.

INTERVIEWFollow-ups they'll ask

  • "What if temperatures can be negative?" The algorithm is unchanged — it only compares adjacent temperatures, never assumes non-negativity.
  • "Can you solve it in O(1) extra space?" The output array is required, so O(n) is unavoidable. The stack is O(n) auxiliary; there is no known O(1)-auxiliary solution for general inputs.
  • "What if the array is circular (wrap-around)?" Double the array (or iterate twice, keeping real indices) — the same trick used in Next Greater Element II (LC 503).
  • "Return the actual warmer day's index instead of the gap?" Change answer[idx] = i - idx to answer[idx] = i.
  • "How would you handle 'next cooler day'?" Flip the comparison to temperatures[i] < temperatures[stack.top] for a monotone increasing stack.

OPTIMAL Monotonic Stack

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

  for (let i = 0; i < n; i++) {
    // While the current day is warmer than the day at the top of the stack,
    // that day's wait is finally over — record the gap.
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const idx = stack.pop()!;
      answer[idx] = i - idx;
    }
    stack.push(i);                     // push current index, wait for something warmer
  }

  // Any index still in the stack never found a warmer day → answer stays 0.
  return answer;
}
Complexity → O(n) time amortized — the inner while looks like it could be O(n) per iteration, but each index is pushed exactly once and popped at most once across the entire loop, so the total work across all iterations is O(n). Space is O(n) for the stack.

ALT 1 Brute force — scan forward for each day

O(n²) time · O(1) extra space

For every day i, walk forward until you hit a strictly warmer day and record the gap j − i; if none exists the answer stays 0.

approach-2.ts
function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const answer = 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]) {
        answer[i] = j - i;
        break;                       // first warmer day wins
      }
    }
  }

  return answer;
}
Note → A long stretch of cooling temperatures forces each day to scan most of the rest of the array, so the worst case is O(n²). A monotonic decreasing stack of indices (the optimal) resolves each day in amortised O(1) for a single O(n) pass.

MNEMONIC The one-liner

"Stack the waiting — when today is warmer, settle every debt from back to front."

TRIGGERS When you see ___ → reach for ___

"days until warmer / next greater element"monotonic decreasing stack of indices
for each element, find next element satisfying a conditionmonotonic stack (push index, pop on match)
stack never has duplicate warmth orderdecreasing monotonic invariant enforced by while-pop
"what if no such day exists?" — default to 0pre-fill answer with 0 before the loop

SKELETON The reusable shape

skeleton.ts
const answer = new Array<number>(n).fill(0);
const stack: number[] = [];   // indices, monotone decreasing by temp

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

FLASHCARDS Tap to flip

What does the stack hold?
Indices (not temperatures) of days still waiting for a warmer successor.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is the time complexity of the monotonic stack approach?
QUESTION 02
What does the stack store in the standard solution?
QUESTION 03
For temperatures = [73,74,75,71,69,72,76,73], what is answer[4]?
QUESTION 04
For a strictly decreasing input like [100, 90, 80, 70], what does answer look like?
QUESTION 05
Why is answer pre-filled with zeros before the loop?
QUESTION 06
What is the worst-case space used by the stack (excluding the output array)?
QUESTION 07
When a new day i is colder than the top of the stack, what happens?
QUESTION 08
#739 · Daily TemperaturesA monotonic decreasing stack of indices yields the next-warmer-day gap in one pass: when a warmer temperature is encountered, pop every cooler index and record the difference as each answer.Which algorithmic approach does this primarily use?
QUESTION 09
#739 · Daily TemperaturesA monotonic decreasing stack of indices yields the next-warmer-day gap in one pass: when a warmer temperature is encountered, pop every cooler index and record the difference as each answer.Which implementation correctly solves it?