Skip to content

Volume ITechnology

4.8.5 — Daily Temperatures ​

LeetCode 739 · Medium

The problem ​

You are given a list called temperatures, one temperature per day. For each day, work out how many days you must wait until a strictly warmer day. If no warmer day ever comes, put 0.

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

Read the first few by hand. Day 0 is 73, and day 1 is 74, which is warmer, so the wait is 1. Day 2 is 75. Days 3, 4 and 5 are all cooler. Day 6 is 76, the first warmer day, so the wait is 6 - 2 = 4. Day 6 is never beaten, so its answer is 0.

There are up to 100,000 days, and each temperature is between 30 and 100.

What the problem is really asking ​

For each day, find the next day to its right with a bigger value. This question has a name: next greater element. It is the single most useful idea in this group of problems.

The brute force, and where it wastes work ​

From each day, scan forward until you find a warmer day.

python
def dailyTemperatures(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
                break
    return answer

If the temperatures keep falling, every scan runs to the end, which is O(n^2). For 100,000 days that is about five billion steps.

The waste in one sentence: a long stretch of cool days gets scanned again and again, once for every earlier day that is waiting to be beaten.

The idea ​

Turn it around. Instead of each day looking forward for its answer, let each new day resolve the earlier days that were waiting for it.

Walk forward through the days. Keep a list of the days that are still waiting for a warmer day. When today arrives, look at the waiting days. Every one that is cooler than today has just found its answer: it is today. Remove those days and write down their waits. Then add today to the waiting list, because today is now waiting for something warmer than itself.

Here is a useful fact about that waiting list. The temperatures in it always go down from the oldest to the newest. Why? Suppose a warmer day arrived while a cooler day was waiting. The cooler day would be resolved straight away and removed. So a cooler day can never be sitting behind a warmer day that came later.

Because the newest waiting days are always the coolest, today only has to check the newest waiting day first. If today beats it, remove it and check the next newest. As soon as today fails to beat one, it cannot beat any older one either, because the older ones are even warmer. So we always work from the newest end. That makes the waiting list a stack.

A stack whose values always go in one direction like this is called a monotonic stack. "Monotonic" means "always moving one way". Here the values always decrease from the bottom of the stack to the top.

The one sentence that unlocks this whole family ​

A monotonic stack does its useful work when an item is popped, not when it is pushed. The pop is the moment you learn something: "this waiting day has just found its warmer day, and it is today." If you ever find yourself trying to work out an answer at push time, you have the model backwards.

The solution ​

python
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)                        # (1)
        stack = []                                              # (2)

        for i, temp in enumerate(temperatures):                 # (3)
            while stack and temperatures[stack[-1]] < temp:     # (4)
                j = stack.pop()                                 # (5)
                answer[j] = i - j                               # (6)
            stack.append(i)                                     # (7)

        return answer                                           # (8)
ts
function dailyTemperatures(temperatures: number[]): number[] {
  const answer = new Array(temperatures.length).fill(0);        // (1)
  const stack: number[] = [];                                   // (2)

  for (let i = 0; i < temperatures.length; i++) {               // (3)
    while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {  // (4)
      const j = stack.pop()!;                                   // (5)
      answer[j] = i - j;                                        // (6)
    }
    stack.push(i);                                              // (7)
  }

  return answer;                                                // (8)
}

Line by line ​

(1) Fill the answer with 0s. Any day that never finds a warmer day should end with 0. By starting every slot at 0, those days are already correct, and we will never need a clean-up step at the end.

(2) The stack of waiting days. It holds positions, not temperatures. The answer is a number of days, which is a difference between two positions. A temperature alone cannot give you that. When we need a waiting day's temperature, we look it up with temperatures[position].

(3) Walk forward through the days. i is today's position and temp is today's temperature.

(4) Does today beat the newest waiting day? stack[-1] is the top of the stack, the newest waiting day. If its temperature is lower than today's, today resolves it. The while keeps going, because today may resolve several waiting days in a row.

We use <, not <=. The problem says strictly warmer. A day with the same temperature does not count, so the earlier day keeps waiting.

(5) Pop the resolved day. j is its position.

(6) Write down its wait. The warmer day is today, at position i, so the wait is i - j days.

(7) Today starts waiting. After resolving everything it can, today goes onto the stack. It is cooler than or equal to everything still below it, so the stack still goes down from bottom to top.

(8) Done. Days still on the stack never found a warmer day, and they already hold 0 from line (1).

Trace ​

Take temperatures = [73, 74, 75, 71, 69, 72, 76, 73]. The stack is shown as temperatures so it is easy to read, but it really holds positions.

iTempPopped (day → wait)Stack after
073—73
174day 0 → 174
275day 1 → 175
371—75, 71
469—75, 71, 69
572day 4 → 1, day 3 → 275, 72
676day 5 → 1, day 2 → 476
773—76, 73

Days 6 and 7 are still on the stack, so they keep their 0. The answer is [1, 1, 4, 2, 1, 1, 0, 0].

Look at row 6. One warm day resolved two waiting days at once. That batching is what makes the method fast.

Complexity, derived ​

Time. There is a while inside a for, but it is not O(n^2). Follow one position through its whole life.

  • It is pushed onto the stack exactly once, at line (7).
  • It is popped at most once, at line (5). Once popped, it never comes back.

So over the whole run there are at most n pushes and at most n pops. That is at most 2n stack operations in total, not per turn. Everything else is constant work per day. So the time is O(n).

This is the same "count the total, not the per-turn work" argument as in 4.4.9 and 4.6.6. You will be asked for it every time you use a monotonic stack.

Space. The answer list has n slots. In the worst case, the temperatures only fall, like [100, 90, 80]. Then nothing is ever popped and the stack holds all n positions. So the space is O(n).

Edge cases ​

  • Temperatures only fall. Nothing is popped. Every answer stays 0.
  • Temperatures only rise. Each day resolves the day before it. The stack never holds more than one day.
  • Equal temperatures, like [75, 75, 75]. Because line (4) uses <, none resolves another. They all wait, and all end with 0.
  • One day. The answer is [0].

The four versions ​

Every "next bigger or smaller" problem is this code with two things changed: the comparison in line (4), and which way you walk.

You wantPop while the top is…Walk
next greater on the rightsmaller than todayleft to right
next smaller on the rightgreater than todayleft to right
next greater on the leftsmaller than todayright to left
next smaller on the leftgreater than todayright to left

Do not memorise the table. Work it out once by asking: "which items am I keeping, and what makes one of them useless?"

Variations you will meet ​

  • Next Greater Element I and II. The same code. In version II the list wraps around in a circle. Walk the list twice, and use i % n to turn a position in the second lap back into a real position. The % sign means "remainder after dividing".
  • Online Stock Span. How many days in a row, ending today, had a price at or below today's? That is "next greater on the left".
  • Largest Rectangle in Histogram. Needs the next smaller bar on both sides. That is 4.8.7, the hardest problem in this group.
  • Remove K Digits. Make the smallest number by deleting k digits. When a smaller digit arrives, pop larger digits before it. Same machinery, different goal.

What the interviewer will push on ​

"Why is this O(n)?" Each position is pushed once and popped at most once.

"Why store positions and not temperatures?" The answer is a distance between positions.

"What is left on the stack at the end?" Days that never found a warmer day. They are already 0.

"Change it to find the next cooler day." Flip < to > in line (4). Doing this without pausing shows you understood the structure.

"Could you walk right to left instead?" Yes. Then the stack holds future days that could be the answer, and you read each day's answer from the top of the stack instead of writing it at pop time. Both are O(n). Left to right is easier to explain, because the pop carries the meaning.

One thing to volunteer: say the rule as one sentence before coding. "A cooler earlier day is resolved the moment a warmer day arrives, so the stack only holds days still waiting, in falling order."

Next: 4.8.6 Car Fleet. A physics puzzle that turns out to be the same idea in disguise.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet