Daily Temperatures [Medium] — Monotonic Stack Masterclass [Amazon, Google]

Problem Statement

Given an array of integers temperatures representing the daily temperatures, return an array answer where answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0.

Example

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

Explanation of output:

Day 0 (73°): day 1 is warmer (74°). Wait = 1.
Day 1 (74°): day 2 is warmer (75°). Wait = 1.
Day 2 (75°): next warmer is day 6 (76°). Wait = 4.
Day 3 (71°): next warmer is day 5 (72°). Wait = 2.
Day 4 (69°): next warmer is day 5 (72°). Wait = 1.
Day 5 (72°): next warmer is day 6 (76°). Wait = 1.
Day 6 (76°): no future day is warmer. Wait = 0.
Day 7 (73°): no future day is warmer. Wait = 0.

Constraints: 1 <= temperatures.length <= 10^5, 30 <= temperatures[i] <= 100

Why This Problem Matters
Brute Force: O(n²)
The Monotonic Stack Insight
Mental Model
Visual Dry Run
The Key Insight: Store Indices, Not Temperatures
Common Mistakes
Solutions
Python — Brute Force O(n²)
Python — Monotonic Stack O(n)
JavaScript — Brute Force O(n²)
JavaScript — Monotonic Stack O(n)
Complexity Analysis
Follow-up Questions
This Pattern Solves
Key Takeaway

Why This Problem Matters

Daily Temperatures is the canonical introduction to the monotonic stack — one of the most valuable patterns in competitive programming and technical interviews. The problem is a direct instance of the "next greater element" problem, which asks: for each element in an array, find the first element to its right that is strictly greater.

This pattern matters for three reasons:

First, it appears everywhere. The same monotonic stack structure solves at least six distinct LeetCode problems — Next Greater Element I (LC 496), Next Greater Element II (LC 503), Online Stock Span (LC 901), Largest Rectangle in Histogram (LC 84), Maximal Rectangle (LC 85), and Trapping Rain Water (LC 42). Learning Daily Temperatures well means you already understand the core of all of them.

Second, it is a classic interview question at Amazon and Google. Both companies use this problem (and close variants) to test whether a candidate can identify the right data structure for a problem. The brute force is obvious; the optimal solution requires a specific insight that non-obvious candidates miss.

Third, it teaches amortized O(n) thinking. The monotonic stack solution contains a while loop nested inside a for loop — the same surface structure as O(n²). Understanding why it is actually O(n) builds the amortized analysis intuition that carries over to many problems.

Brute Force: O(n²)

The most direct approach: for each day i, scan every subsequent day j > i until you find a temperature strictly greater than temperatures[i]. Record j - i as the wait, or leave it as 0 if you exhaust the array without finding anything warmer.

For day 2 (75°): check day 3 (71°) — cooler. Check day 4 (69°) — cooler.
Check day 5 (72°) — cooler. Check day 6 (76°) — WARMER. Answer = 6 - 2 = 4.

This is correct, but for an array of length n it performs up to n*(n-1)/2 comparisons in the worst case (e.g., a strictly descending temperature sequence like [100, 99, 98, ..., 1] where every element scans the entire remaining array before concluding there is no warmer day). That is O(n²) time, which times out on LeetCode's constraints of up to 100,000 elements.

We need something smarter. The brute force repeats work because it answers each day's question independently. If we could share information between days — "day 2 and day 3 are both waiting for something warmer than them, and day 6 answers both questions at once" — we could solve every day's question in a single pass.

That is exactly what the monotonic stack does.

The Monotonic Stack Insight

A monotonic stack is a stack that maintains its elements in a consistent order — either always increasing or always decreasing from bottom to top. For this problem we use a monotonic decreasing stack: the temperatures corresponding to indices in the stack are always decreasing from bottom to top (the bottom index has the highest temperature, the top index has the lowest).

Here is the core rule:

Whenever we encounter a temperature that is warmer than the temperature at the top of the stack, that warmer day is the "next greater element" for the top of the stack — and for any other stack element it is also greater than.

More concretely:

Iterate through temperatures left to right, keeping a stack of indices (not temperatures).
Before pushing the current index i, pop every index j from the stack where temperatures[i] > temperatures[j]. For each popped j, record answer[j] = i - j.
Push i onto the stack.
After the full iteration, any index still in the stack never found a warmer day — its answer stays 0 (which is the default).

Why does this work? Because of the invariant we maintain: the stack always holds indices in decreasing order of temperature. Any index on the stack is "waiting" for a future temperature higher than its own. The moment we see a temperature t at index i that exceeds temperatures[stack.top()], we know i is the earliest future day that is warmer — by definition, because if there had been any earlier day warmer than stack.top(), that earlier day would have already popped stack.top() when it was processed.

This is the same logic that makes binary search work: by maintaining a structural invariant, we gain the ability to make strong claims without exhaustive search.

Mental Model

Imagine a queue of people waiting at a bus stop. Each person has a sign displaying their "minimum acceptable temperature" to go outside. They join the back of the queue over time (as days pass). When a warm day arrives, anyone in the queue whose threshold is met or exceeded steps out. The warm day satisfies all of them at once.

In our algorithm, the stack is the queue. Each person in the queue corresponds to an index j waiting for a temperature higher than temperatures[j]. When day i arrives with temperature temperatures[i], it "satisfies" every person in the queue with a lower threshold. The wait for each satisfied person is simply i - j.

The key efficiency gain: a single warm day can clear out many waiting people in one sweep. Across the entire array, each person enters the queue exactly once and leaves exactly once — so the total work is O(n), even though on any given day many people might leave simultaneously.

Visual Dry Run

Input: [73, 74, 75, 71, 69, 72, 76, 73] Initial state: stack = [], answer = [0, 0, 0, 0, 0, 0, 0, 0]

i = 0, temp = 73 Stack is empty — nothing to pop. Push 0.

stack = [0]          (temps: [73])
answer = [0,0,0,0,0,0,0,0]

i = 1, temp = 74 74 > temperatures[0] = 73 → pop index 0. answer[0] = 1 - 0 = 1. Stack now empty — nothing more to pop. Push 1.

stack = [1]          (temps: [74])
answer = [1,0,0,0,0,0,0,0]

i = 2, temp = 75 75 > temperatures[1] = 74 → pop index 1. answer[1] = 2 - 1 = 1. Stack empty. Push 2.

stack = [2]          (temps: [75])
answer = [1,1,0,0,0,0,0,0]

i = 3, temp = 71 71 < temperatures[2] = 75 → do NOT pop. Push 3.

stack = [2, 3]       (temps: [75, 71])
answer = [1,1,0,0,0,0,0,0]

i = 4, temp = 69 69 < temperatures[3] = 71 → do NOT pop. Push 4.

stack = [2, 3, 4]    (temps: [75, 71, 69])
answer = [1,1,0,0,0,0,0,0]

i = 5, temp = 72 72 > temperatures[4] = 69 → pop index 4. answer[4] = 5 - 4 = 1. 72 > temperatures[3] = 71 → pop index 3. answer[3] = 5 - 3 = 2. 72 < temperatures[2] = 75 → STOP. Push 5.

stack = [2, 5]       (temps: [75, 72])
answer = [1,1,0,2,1,0,0,0]

i = 6, temp = 76 76 > temperatures[5] = 72 → pop index 5. answer[5] = 6 - 5 = 1. 76 > temperatures[2] = 75 → pop index 2. answer[2] = 6 - 2 = 4. Stack empty. Push 6.

stack = [6]          (temps: [76])
answer = [1,1,4,2,1,1,0,0]

i = 7, temp = 73 73 < temperatures[6] = 76 → do NOT pop. Push 7.

stack = [6, 7]       (temps: [76, 73])
answer = [1,1,4,2,1,1,0,0]

End of array. Indices 6 and 7 remain on the stack — they never found a warmer day. Their answers stay 0.

Final answer: [1, 1, 4, 2, 1, 1, 0, 0] ✓

The Key Insight: Store Indices, Not Temperatures

The single most important implementation detail is: the stack stores indices, not temperatures.

There are two reasons this matters:

You need the index to compute the wait. The answer for day j is current_index - j. If you only stored the temperature, you would not have j and could not compute the wait.
You can always look up the temperature from the index. temperatures[j] gives you the temperature at index j. Storing indices gives you everything: both the position (to compute the wait) and the temperature (to maintain the monotonic invariant).

This sounds obvious once stated, but storing temperatures in the stack is one of the most common first-attempt mistakes, and it silently produces wrong answers rather than an obvious error.

Common Mistakes

Mistake 1 — Storing temperatures instead of indices in the stack. If you push temperatures onto the stack, you cannot compute answer[j] = i - j because you no longer have j. You might try to work around this by also maintaining a separate index-tracking structure, but that complexity signals you took the wrong approach. Always push indices; the temperature is always recoverable via temperatures[stack_top].

Mistake 2 — Using a monotonic increasing stack instead of decreasing. A monotonic increasing stack (bottom to top: ascending temperatures) would pop elements when the current temperature is lower, not higher. This would answer "next cooler day" rather than "next warmer day." The direction of the stack's monotonicity must match the direction of the comparison: to find the next greater element, use a decreasing stack and pop when you find something greater.

Mistake 3 — Using >= instead of > in the comparison. The problem asks for a strictly warmer day. Using >= causes equal temperatures to trigger a pop, which incorrectly treats "same temperature" as "warmer." Always use strict > here.

Mistake 4 — Forgetting that unresolved indices default to 0. Elements remaining on the stack after the full iteration never found a warmer day. Their answer is 0. If you initialize the answer array with 0s before the loop (which you should), this is handled automatically — no extra pass needed. Attempting to explicitly set these to 0 after the loop by iterating the stack is unnecessary and error-prone.

Solutions

Python — Brute Force O(n²)

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n

    for i in range(n):
        # Scan every day after i looking for the first warmer day
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # number of days to wait
                break               # stop at the FIRST warmer day

    return answer
# Time: O(n²)  Space: O(1) extra (output array excluded)

Python — Monotonic Stack O(n)

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # stores indices; temperatures at those indices are decreasing

    for i, temp in enumerate(temperatures):
        # While the current day is warmer than the day at the top of the stack,
        # the current day is the "next warmer" answer for the stack top.
        while stack and temp > temperatures[stack[-1]]:
            j = stack.pop()         # j is the index waiting for a warmer day
            answer[j] = i - j       # days waited = current index - waiting index

        stack.append(i)  # current day has not yet found its warmer day; push it

    # Any indices left in the stack never found a warmer day → answer stays 0
    return answer
# Time: O(n) amortized — each index is pushed once and popped at most once
# Space: O(n) for the stack in the worst case (descending temperatures)

JavaScript — Brute Force O(n²)

var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);

    for (let i = 0; i < n; i++) {
        // Scan forward from i+1 to find the first warmer day
        for (let j = i + 1; j < n; j++) {
            if (temperatures[j] > temperatures[i]) {
                answer[i] = j - i;  // days to wait
                break;              // stop at the first warmer day
            }
        }
        // If inner loop exhausts without break, answer[i] stays 0
    }

    return answer;
    // Time: O(n²)  Space: O(1) extra
};

JavaScript — Monotonic Stack O(n)

var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);
    const stack = [];  // stack of indices; monotonically decreasing by temperature

    for (let i = 0; i < n; i++) {
        // Pop every index whose temperature is strictly less than the current day's
        while (stack.length > 0 && temperatures[i] > temperatures[stack.at(-1)]) {
            const j = stack.pop();    // index j was waiting for a warmer day
            answer[j] = i - j;       // current day i is the answer for day j
        }

        stack.push(i);  // day i is now waiting for its own warmer future day
    }

    // Indices remaining in the stack have no future warmer day → answer stays 0
    return answer;
    // Time: O(n) amortized  Space: O(n) worst case
};

Complexity Analysis

Approach	Time	Space	Notes
Brute force	O(n²)	O(1) extra	Times out at n = 10^5
Monotonic stack	O(n) amortized	O(n)	Each index pushed/popped at most once

Why the monotonic stack is O(n) despite the nested while loop:

The while loop is nested inside the for loop, which at first glance suggests O(n²). The key insight is that work in the while loop is bounded across the entire algorithm, not per iteration.

Each index is pushed onto the stack exactly once and popped from the stack at most once. There are n indices total, so there are at most n pushes and at most n pops. The total number of operations across all iterations of the for loop is therefore at most 2n — that is O(n).

This is amortized O(n): individual iterations of the outer loop may trigger many pops (if there is a long run of days waiting for a single warm day), but the "budget" for those pops is shared across the entire execution. No index can be popped more than once, so the total pop count never exceeds n.

Worst case for stack space: A strictly descending temperature sequence like [100, 99, 98, ..., 1] results in every index being pushed but never popped during the loop (no day is ever warmer than any previous day), so the stack grows to size n. The output array also requires O(n) space, but since it is required output it is not counted as auxiliary space.

Follow-up Questions

Understanding the monotonic stack pattern in Daily Temperatures unlocks these related problems directly:

Next Greater Element II — LC 503 (Circular Array) The same problem, but the array wraps around: after the last element comes the first. The trick is to simulate doubling the array by iterating 2n times with i % n for the actual index. The stack still holds indices from the original (0 to n-1) range; the second pass only resolves waiting indices, it does not add new ones.

Online Stock Span — LC 901 Given stock prices arriving one at a time, return the "span" — the number of consecutive preceding days (including today) where the price was less than or equal to today's price. This is the reverse direction: instead of "next greater," it is "previous greater or equal." Use a monotonic decreasing stack of (price, span) pairs. When a new price arrives, pop all pairs with price ≤ current price, accumulating their spans into the current day's span.

Largest Rectangle in Histogram — LC 84 For each bar, you need the distance to the nearest shorter bar on both the left and the right. Two monotonic stack passes (or one clever combined pass) give you the left and right boundaries for every bar in O(n). This is harder but uses the same "pop when the invariant breaks" logic.

Next Greater Element I — LC 496 (Simpler variant) Given two arrays nums1 (a subset of nums2), find for each element in nums1 its next greater element in nums2. Build a HashMap using a monotonic stack pass over nums2, then look up each element of nums1 in O(1). The core stack logic is identical to Daily Temperatures.

This Pattern Solves

The monotonic stack "process when the invariant breaks" pattern appears whenever you need to find, for each element, the nearest element satisfying a condition (greater, smaller, equal) in one direction (left or right). Recognizing the pattern is the skill:

Next greater element to the right → monotonic decreasing stack, pop when current > top.
Next smaller element to the right → monotonic increasing stack, pop when current < top.
Previous greater element to the left → same stacks, but iterate right to left.
Span counting → monotonic decreasing stack, accumulate span on pop.
Rectangle area → monotonic increasing stack, compute area on pop using height × width.

If you can identify which variant of "nearest element satisfying a condition" your problem maps to, the implementation follows mechanically.

Key Takeaway

Daily Temperatures is the "next greater element" problem with a concrete, intuitive framing. The brute force checks every pair of days in O(n²); the monotonic stack answers every day's question in a single O(n) pass by exploiting the invariant that any warm day resolves all waiting cooler days at once. The two things to remember: store indices in the stack (not temperatures), and push to the stack after resolving the while loop, so every element participates in at most one push and one pop across the entire algorithm. Master this pattern here and you have the foundation for Largest Rectangle in Histogram, Online Stock Span, Trapping Rain Water, and the Next Greater Element family — six problems for the price of one.