Daily Temperatures: Learning to Store a Distance, Not a Value

In our last post we learned the next greater element — for each number, find the next bigger one to its right. Today's problem, "daily temperatures", is that exact same idea with one small but interesting twist. Instead of asking "what is the next warmer day?", it asks "how many days do I have to wait until a warmer day?"

That tiny change — from what to how far — is the whole lesson of this post. And do not worry if the monotonic stack still feels a little slippery from last time. I am going to explain everything from the ground up again, slowly, as if this were your very first time seeing it. By the end, I promise it will feel natural.

The Problem

You are given a list of daily temperatures. For each day, you must answer a simple human question:

"Starting from tomorrow, how many days will I have to wait before it gets warmer than today? If it never gets warmer, just write 0."

Let us look at a concrete example:

Day:          0    1    2    3    4    5    6    7
Temperature:  73   74   75   71   69   72   76   73
Answer:       1    1    4    2    1    1    0    0

Let us slowly read a few of these so the meaning is crystal clear before we touch any code.

• Day 0 (73°): Tomorrow, day 1, is 74°. That is warmer! So I waited just 1 day.
• Day 2 (75°): Now look what happens. Day 3 is 71° (colder), day 4 is 69° (colder), day 5 is 72° (still colder), day 6 is 76° (finally warmer!). Day 6 minus day 2 is 4 days of waiting.
• Day 6 (76°): After this, the only day left is day 7 at 73°, which is colder. It never gets warmer, so the answer is 0.

Notice the answer is a count of days — a distance — not a temperature. Hold on to that thought, because it is the one thing that makes this problem slightly different from the last one.

First, the Obvious Way (So We Understand the Problem)

Before reaching for anything clever, let us solve it the plain, honest way. For each day, we simply walk forward, day by day, until we find a warmer one, counting steps as we go:

function dailyTemperaturesBrute(temps) {
    let n = temps.length;
    let answer = new Array(n).fill(0);

    for (let i = 0; i < n; i++) {
        // start looking from the very next day
        for (let j = i + 1; j < n; j++) {
            if (temps[j] > temps[i]) {
                answer[i] = j - i;  // number of days we waited
                break;              // stop at the FIRST warmer day
            }
        }
    }

    return answer;
}

Read this carefully, because it is the clearest possible statement of what we want:

• The outer loop picks a day i.
• The inner loop starts at j = i + 1 (tomorrow) and steps forward.
• The moment temps[j] > temps[i], we found the first warmer day. The distance is j - i. We write it and break immediately, because we only care about the first one.
• If the inner loop finishes without finding anything warmer, answer[i] stays at its starting value of 0.

This is 100% correct. So why do we not stop here?

Because of how much work it does. Imagine the temperatures keep dropping, like [80, 79, 78, 77]. For day 0, the inner loop runs all the way to the end and finds nothing. For day 1, it runs almost to the end. And so on. When every day has to scan most of the array, the total work grows like n × n — that is O(n²). For a few thousand days that is fine, but for a very long list it becomes painfully slow, and an interviewer will ask you to do better.

The good news: we can find every answer in a single walk through the list. Let us build up to it gently.

The Big Idea, Explained From Scratch

Here is the mental shift that unlocks everything. It is worth reading twice.

The brute force makes each day look forward for its own answer. That is wasteful because the same future days get scanned over and over. So instead, we are going to turn the problem inside out:

Rather than each day searching forward for a warmer day, we let each new day announce itself and settle the debts of all the earlier days that were waiting for exactly this warmth.

Let me make that concrete with a story. Picture the days standing in a line, each holding up a sign with their temperature. As we walk through them one by one, some days are "still waiting" — they have not yet seen a warmer day. Now a new, warmer day walks in. It looks back at the waiting days and says: "You there, and you, and you — you were all colder than me, and I am the first warmer day you'll meet. Your wait is over. Here is your answer." Then those satisfied days leave the line, and the new day joins the back of the line to wait for its own warmer day.

The line of "still waiting" days is exactly what we will keep in a stack. And here is the crucial property: the days in that line are always in decreasing temperature order from bottom to top. Why must that be true? Because the moment a warmer day arrives, it removes every cooler day that was waiting — so a cooler day can never sit on top of a warmer one. A stack that always stays sorted like this is what we call a monotonic stack. You do not have to sort it yourself; it stays sorted automatically as a side effect of the rule "a warm day evicts the cooler waiting days."

That is the entire trick. Everything below is just that story, written in code.

Why a Stack, and Why Store Indices?

Two small questions a beginner rightly asks:

"Why a stack and not a plain array or a queue?" Because we always deal with the most recently added waiting day first. When a warm day arrives, the day it satisfies last (the coldest, most recent one) is right on top, easy to reach. "Most recent first" is the exact definition of a stack — last in, first out. A queue (first in, first out) would give us the wrong end.

"Why store the index i and not the temperature itself?" Because the answer is a distance: warmerDay - waitingDay. To compute a distance we need positions, not values. So we push the index onto the stack. When we need the temperature for a comparison, we just look it up with temps[index]. This "store the index, look up the value when needed" habit will serve you in almost every monotonic-stack problem.

The Elegant O(n) Solution

function dailyTemperatures(temps) {
    let n = temps.length;
    let answer = new Array(n).fill(0);
    let stack = []; // indices of days still waiting for a warmer day

    for (let i = 0; i < n; i++) {
        // today (temps[i]) is warmer than the day waiting on top of the stack?
        // then today is exactly the warmer day that day was waiting for.
        while (stack.length > 0 && temps[i] > temps[stack[stack.length - 1]]) {
            let prevDay = stack.pop();        // the waiting day, now satisfied
            answer[prevDay] = i - prevDay;    // distance = how long it waited
        }

        // today has no warmer day yet, so it joins the line of waiting days
        stack.push(i);
    }

    // any day still on the stack never saw a warmer day → its answer stays 0
    return answer;
}

let temps = [73, 74, 75, 71, 69, 72, 76, 73];
console.log(dailyTemperatures(temps)); // [1, 1, 4, 2, 1, 1, 0, 0]

Walking Through the Code, Line by Line

Let us go slowly and make sure not a single line feels like magic.

Setting up:

let answer = new Array(n).fill(0);
let stack = [];

We create the answer array and fill it with 0 right away. This is a small but clever choice: 0 is the correct answer for any day that never gets warmer, so we only ever have to overwrite the days that do find a warmer day. The days that never do are already correct and we can happily ignore them. The stack starts empty — nobody is waiting yet.

The outer loop:

for (let i = 0; i < n; i++) {

We walk through the days one time, left to right. Just once. That single pass is what makes this fast.

The while loop — read this as an English sentence:

while (stack.length > 0 && temps[i] > temps[stack[stack.length - 1]]) {
    let prevDay = stack.pop();
    answer[prevDay] = i - prevDay;
}

In plain words: "While there is somebody waiting, and today is warmer than the day currently on top of the waiting line — then today is that day's warmer day, so hand them their answer and remove them from the line."

Let us dissect the condition, because two things must both be true:

• stack.length > 0 — there is actually someone waiting. If the line is empty, there is nobody to satisfy, so we skip the loop. (Checking this first also protects us: it means the second part never tries to peek at an empty stack.)
• temps[i] > temps[stack[stack.length - 1]] — stack[stack.length - 1] is the index sitting on top of the stack (the most recent waiting day). We look up its temperature and compare. If today is strictly warmer, this waiting day's search is over.

Inside the loop:

• let prevDay = stack.pop(); — remove the top waiting day and remember which day it was.
• answer[prevDay] = i - prevDay; — the distance from that day (prevDay) to today (i) is exactly how many days it waited. We write it in.

And notice it is a while, not an if — because a single warm day might satisfy several waiting days at once. Remember day 6 (76°) in our example? It was warmer than day 5, and also warmer than day 4 and day 3 which were still waiting behind day 5. So it pops all of them, one after another, in a single visit. The while keeps popping until either the line is empty or it hits a day that is not colder than today.

Joining the line:

stack.push(i);

After today has satisfied everyone it could, today itself has no warmer day yet. So it steps to the back of the waiting line by pushing its index onto the stack. Maybe some future warm day will satisfy it; maybe not.

After the loop ends:

Whatever indices are still on the stack are days that never met a warmer day. But we filled answer with 0 at the start, so those positions already hold the correct value. We do not need to touch them. Clean.

Let Us Trace It Slowly

This is the best way to make the idea stick. Temperatures [73, 74, 75, 71, 69, 72, 76, 73]. I will show the stack as a list of indices (bottom → top), and note every answer the moment it is written.

The loop ends. Indices 6 and 7 are still waiting, so answer[6] and answer[7] keep their starting value of 0.

Final answer: [1, 1, 4, 2, 1, 1, 0, 0]. Look back at day 5 in the table — see how a single warmer day (72°) settled two waiting days in one go? And day 6 (76°) reached all the way back to satisfy day 2, which had been patiently waiting since the very start. That reaching-back is the monotonic stack doing its quiet work.

Why Is This O(n) and Not O(n²)?

This trips up a lot of people, so let us reason about it carefully. "There is a while loop inside a for loop — surely that is O(n²)?" It looks that way, but it is not, and here is the honest argument:

Think about the life of a single day's index. It gets pushed onto the stack exactly once (when we reach it in the outer loop). And it gets popped at most once (when some warmer day finally satisfies it). After it is popped, it is gone forever — it never comes back.

So across the entire run of the algorithm, the total number of pushes is n, and the total number of pops is at most n. That is at most 2n stack operations in total, no matter how the while loop bunches them up on any particular step. 2n operations means O(n) time. This style of counting — "count the total work over the whole run, not the worst case of one step" — is called amortised analysis, and being able to explain it out loud is a genuine green flag in an interview.

• Time: O(n) — each index is pushed once and popped at most once.
• Space: O(n) — in the worst case (temperatures that only ever fall, like [80, 79, 78]), nobody ever gets satisfied, so every index piles up on the stack at the same time.

Final Thoughts

Daily temperatures teaches one precise, portable lesson on top of what next-greater-element already gave us:

The monotonic stack does not force you to store the value you found. You can store an index instead and compute a distance — or store anything else you can derive from position.

That freedom is exactly why this one pattern stretches to cover so many problems. Once you internalise "let the newcomer resolve the waiting ones, and store whatever the question actually asks for," you will meet the same shape again in the largest rectangle in a histogram, in trapping rain water, and in half a dozen other problems that look intimidating from the outside but are this friendly loop on the inside.

Take your time with the trace table above. Draw the stack on paper. Once you see day 6 reach back and settle day 2, this pattern is yours for life.

Happy coding, and all the best for your interviews!