Skip to content
16-Week DSA Roadmap
LeetCode #739MediumProblem 4 of 8

Daily Temperatures

For each day, count how many days you have to wait for a warmer one.

  • Monotonic stack
  • Next greater element

Before this, know: What a stack is (push, pop, peek), Arrays and indexes

The problem in plain English

You get a list temperatures, one number per day. For each day, answer the question: “how many days until it’s warmer than today?” If no warmer day ever comes, the answer for that day is 0. Return all the answers as a list.

Take temperatures = [73, 71, 69, 72, 76]. Day 0 is 73°. The next day warmer than 73° is day 4 (76°), so day 0 waits 4 days. Day 2 is 69°, and the very next day (72°) is warmer, so it waits 1 day.

73°4071°2169°1272°1376°04
Each bar is a day; the number above it is the answer. Day 0 (73°) waits 4 days for 76°. Day 4 is the warmest and never sees a warmer day, so its answer is 0.

So the answer is [4, 2, 1, 1, 0]. Rules that matter:

  • “Warmer” means strictly warmer. Equal doesn’t count.
  • There can be up to 100,000 days, with temperatures between 30 and 100.

Before you code: think it through

Here is the key observation. When a new day arrives, the days still waiting for a warmer day always have temperatures that go down as you move to the most recent one. Why? If an older waiting day were colder than a newer one, the newer one would already have been its warmer day, and it would have stopped waiting.

Pause and think

It's day 3 (72°). Days 0, 1, 2 (73°, 71°, 69°) are still waiting. Which of them does 72° answer, and in what order do you check them?

Approach 1: Brute force

For each day, walk forward one day at a time until a warmer day shows up. The distance is the answer. If we hit the end, the answer stays 0.

Brute force: look forward from every day

temperatures = [73, 71, 69, 72, 76]

temperatures — later days looked at so far: 0
73°071°169°272°376°4↑i
answer
  1. 00
  2. 01
  3. 02
  4. 03
  5. 04
  • Day i
  • Later day j
  • First warmer day
  • Answer known

Day 0 (73°): walk forward, one day at a time, until we find a warmer day.

Step 1 / 14

Which line is running?

function dailyTemperatures(temperatures) {  const n = temperatures.length;  const answer = new Array(n).fill(0);Running now:   for (let i = 0; i < n; i++) {    for (let j = i + 1; j < n; j++) {      if (temperatures[j] > temperatures[i]) {        answer[i] = j - i; // first warmer day found: stop looking        break;      }    }  }  return answer;}

Brute force: look forward from every day

function dailyTemperatures(temperatures) {  const n = temperatures.length;  const answer = new Array(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; // first warmer day found: stop looking        break;      }    }  }  return answer;}
def daily_temperatures(temperatures):    n = len(temperatures)    answer = [0] * n    for i in range(n):        for j in range(i + 1, n):            if temperatures[j] > temperatures[i]:                answer[i] = j - i  # first warmer day found: stop looking                break    return answer

new Array(n).fill(0) (JavaScript) and [0] * n (Python) both make a list of n zeros, so any day we never fill keeps the answer 0.

Why is it slow?

On a list that only gets colder, like [30, 29, 28, …], no day ever finds a warmer one, so every day walks all the way to the end. With 5 days that’s 4 + 3 + 2 + 1 = 10 looks. With 100,000 days it’s about 100,000 × 100,000 ÷ 2 = 5,000,000,000 looks. That’s O(n²): double the days, four times the work.

The pattern: monotonic stack

A monotonic stack is a stack whose values always go in one direction from bottom to top: always getting smaller (decreasing) or always getting bigger (increasing). “Monotonic” just means “moving one way only”. We keep it that way by popping items before pushing a new one that would break the order.

Pattern

Monotonic stack (next greater element)

Template

Use it when: for each item you need the NEXT (or previous) item that is bigger or smaller than it.

Signal words

  • “next greater”
  • “next warmer”
  • “how many days until”
  • “next larger element”
  • “stock span”

We store indexes (day numbers) on the stack, not temperatures. From an index we can always look up the temperature, and we need the index to work out the distance i − j.

Approach 2: Monotonic decreasing stack

  1. Make answer, a list of zeros, and an empty stack of day indexes.
  2. Walk through the days. Call today’s index i.
  3. While the stack isn’t empty and today is warmer than the day on top: pop that day j and write answer[j] = i − j.
  4. Push today’s index i. It now waits for its own warmer day.
  5. When the loop ends, every day still on the stack never found a warmer day; their answer stays 0.

Press Play. Bars waiting on the stack are shaded; when a warm day arrives, watch it knock out the colder bars one by one, and the answers appear above them (and in the answer row). Then try the edge cases: when it only gets colder, nothing is ever popped; with equal days, 70° does not pop 70°.

Monotonic stack of waiting days

temperatures = [73, 71, 69, 72, 76]

temperatures (bars) — the number above a bar is its answer
73°071°169°272°376°4
stackdecreasing temps
  1. empty
answer
  1. 00
  2. 01
  3. 02
  4. 03
  5. 04
  • Today (i)
  • Waiting on the stack
  • Top of stack, being compared
  • Answer just written
  • Answer known

Every answer starts at 0 ("no warmer day"). The stack will hold the days that are still waiting for a warmer day. Their temperatures go DOWN (or stay equal) from bottom to top.

Step 1 / 23

Which line is running?

function dailyTemperatures(temperatures) {  const answer = new Array(temperatures.length).fill(0);Running now:   const stack = []; // indexes of days still waiting for a warmer day  for (let i = 0; i < temperatures.length; i++) {    // today is warmer than the day on top: that day's wait is over    while (stack.length > 0 && temperatures[i] > temperatures[stack.at(-1)]) {      const j = stack.pop();      answer[j] = i - j;    }    stack.push(i); // today waits for its own warmer day  }  return answer;}

The code, line by line

Monotonic stack

function dailyTemperatures(temperatures) {  const answer = new Array(temperatures.length).fill(0);  const stack = []; // indexes of days still waiting for a warmer day  for (let i = 0; i < temperatures.length; i++) {    // today is warmer than the day on top: that day's wait is over    while (stack.length > 0 && temperatures[i] > temperatures[stack.at(-1)]) {      const j = stack.pop();      answer[j] = i - j;    }    stack.push(i); // today waits for its own warmer day  }  return answer;}
def daily_temperatures(temperatures):    answer = [0] * len(temperatures)    stack = []  # indexes of days still waiting for a warmer day    for i, temp in enumerate(temperatures):        # today is warmer than the day on top: that day's wait is over        while stack and temp > temperatures[stack[-1]]:            j = stack.pop()            answer[j] = i - j        stack.append(i)  # today waits for its own warmer day    return answer

The two versions line up line for line until line 9, where JavaScript has a closing }; after that, JavaScript is one line ahead.

  • Line 1: define the function. (LeetCode wraps it as var dailyTemperatures = function(temperatures) in JavaScript, or a method of class Solution in Python.)
  • Line 2: a list of zeros, one per day. Zero is the right answer for any day that never gets popped.
  • Line 3: the stack of indexes of days still waiting.
  • Line 4: walk through the days. Python’s enumerate gives us both the index i and the temperature temp.
  • Line 6: the heart of the pattern. stack.at(-1) / stack[-1] is the index on top. We keep popping while today is warmer, because one warm day can end the wait of several colder days at once. The stack.length > 0 / stack and part comes first so we never look at the top of an empty stack.
  • Line 7: pop the waiting day j.
  • Line 8: its answer is the distance from j to today.
  • Line 10 (JS) / line 9 (Py): push today. It goes on top of days that are all at least as warm, so the stack stays decreasing.
  • Line 12 (JS) / line 10 (Py): return the answers.

Dry run

Trace temperatures = [73, 71, 69, 72, 76]. The stack shows indexes with their temperatures, bottom → top.

itemppops (j: answer[j] = i − j)stack afteranswer after
073°—[0:73][0, 0, 0, 0, 0]
171°— (71 is not > 73)[0:73, 1:71][0, 0, 0, 0, 0]
269°— (69 is not > 71)[0:73, 1:71, 2:69][0, 0, 0, 0, 0]
372°2: 1, then 1: 2 (stop at 73)[0:73, 3:72][0, 2, 1, 0, 0]
476°3: 1, then 0: 4[4:76][4, 2, 1, 1, 0]
temperatures = [73, 71, 69, 72, 76]

The 72° row (i = 3) shows the payoff: one warm day (72°) answers two waiting days at once, and it stops at 73° without looking any further down.

Complexity

Brute force

Time

O(n²)

Each day may walk to the end of the list: about n × n ÷ 2 looks.

Space

O(1) extra

Only two indexes, besides the answer list we must return anyway.

Monotonic stack

Time

O(n)

Each day is pushed exactly once and popped at most once, so all the while-loop pops add up to at most n, even though the loop is nested.

Space

O(n)

If temperatures only fall, every day waits on the stack at the same time.

The nested while loop looks like O(n²), but it isn’t. Count pushes and pops instead of loop turns: each day is pushed once and popped at most once, so the total work is at most 2n steps. This “count what happens to each item” trick is called amortized analysis.

Common mistakes and edge cases

What to say out loud, in this order:

  1. Restate: “for each day, the distance to the next strictly warmer day, or 0.”
  2. Brute force: “scan forward from each day, O(n²) on a falling list.”
  3. Key insight: “the days still waiting always have decreasing temperatures, and a new day settles the most recent ones first, so a monotonic stack of indexes.”
  4. Explain why it’s O(n) even with the nested loop: each index is pushed and popped at most once.
  5. Dry-run a day that pops two waiting days at once.

Likely follow-up questions:

  • “Next smaller element instead?” Flip the comparison: keep an increasing stack.
  • “Previous greater element?” Same stack; read the top after popping, before pushing.
  • “Can you do it with O(1) extra space?” Yes: walk from the right and use the answers already computed to jump ahead. A nice follow-up to mention, not required.

Related problems:

  • Car Fleet (this week): another stack that only keeps items that “still matter”, after sorting.
  • Largest Rectangle in Histogram (LeetCode 84, a good extra challenge): the hardest monotonic-stack classic.
  • The week 3 overview has the reusable template.