Daily Temperatures: the monotonic stack as a deferred-answer machine

The problem is deceptively direct. You have an array of daily temperatures; for each day, return how many days you have to wait until a strictly warmer one arrives. If none does, return 0.

That framing hides the real question: how do you efficiently know, for every index, where the next larger value sits? The naive answer — look forward from each position — works but revisits every comparison. The better answer is to flip the relationship: rather than each index hunting forward, let a later index announce itself to everyone it outranks. That announcement is a stack pop.

The problem

Given an array of integers temperatures representing daily temperatures, return an array answer where answer[i] is the number of days after day i you must wait to get a strictly warmer temperature; if no such future day exists, answer[i] is 0. Full statement: LeetCode 739.

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

What the constraints force

Temperatures run from 30 to 100. The array length goes up to 10^5. Those two numbers do completely different work.

n <= 10^5 kills O(n²) immediately. Ten thousand days squared is ten billion comparisons. On a typical interview server that is around five seconds of wall time, which is why the problem even exists. Any solution that nests a loop over all future days for each current day fails this constraint.

The temperature range 30 <= temperatures[i] <= 100 is narrower and more interesting. There are exactly 71 distinct temperatures. That means instead of a general stack holding arbitrary values, you could track, for each possible temperature, the most recent index where it appeared. When you arrive at day i with temperature t, the answer for i is the nearest future index among all temperatures t+1 through 100. This is the array-based approach described at the end, and it is a direct consequence of reading the constraint.

The constraint also tells you something about equal temperatures: temperatures[j] > temperatures[i] is strict, so two equal consecutive days do not count. An index stays in the stack until something strictly larger arrives.

Approach 1: brute force

Walk forward from each index and scan right until you find a larger value.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        result = [0] * n
 
        for i in range(n - 1):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    result[i] = j - i
                    break
 
        return result

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        int n = temperatures.Length;
        int[] result = new int[n];
 
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    result[i] = j - i;
                    break;
                }
            }
        }
 
        return result;
    }
}

The last index is never touched by the outer loop — its answer is already 0 from initialization.

Time: O(n²). Worst case is a strictly decreasing array: every index scans the entire remainder and never breaks early.

Space: O(1) auxiliary, not counting the output array.

This is the right starting point for thinking about the problem, and it is correct. It just does not survive n = 10^5 within time limits.

Approach 2: monotonic stack

The insight is in reversing who does the work. In brute force, each index i asks "who is larger than me?" In the stack approach, each index i asks the reverse: "are there any unresolved indices I am larger than?" That reversal lets you settle multiple open accounts at once.

The stack stores indices of days that have not yet found a warmer day. It is monotonically decreasing in temperature: if you look from bottom to top, temperatures only decrease. That invariant is maintained by popping everything you beat before pushing yourself.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        result = [0] * n
        stack = []  # stores indices, temperatures[stack[-1]] is the current minimum
 
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                prev = stack.pop()
                result[prev] = i - prev
            stack.append(i)
 
        return result

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        int n = temperatures.Length;
        int[] result = new int[n];
        var stack = new Stack<int>();
 
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()]) {
                int prev = stack.Pop();
                result[prev] = i - prev;
            }
            stack.Push(i);
        }
 
        return result;
    }
}

Hand trace: [73, 74, 75, 71, 69, 72, 76, 73]

i=0, temp=73: stack empty, push 0        stack=[0]         result=[0,0,0,0,0,0,0,0]
i=1, temp=74: 74>73 -> pop 0, result[0]=1-0=1, push 1    stack=[1]         result=[1,0,0,0,0,0,0,0]
i=2, temp=75: 75>74 -> pop 1, result[1]=2-1=1, push 2    stack=[2]         result=[1,1,0,0,0,0,0,0]
i=3, temp=71: 71<75, push 3              stack=[2,3]       result=[1,1,0,0,0,0,0,0]
i=4, temp=69: 69<71, push 4              stack=[2,3,4]     result=[1,1,0,0,0,0,0,0]
i=5, temp=72: 72>69 -> pop 4, result[4]=5-4=1
              72>71 -> pop 3, result[3]=5-3=2
              72<75, push 5              stack=[2,5]       result=[1,1,0,2,1,0,0,0]
i=6, temp=76: 76>72 -> pop 5, result[5]=6-5=1
              76>75 -> pop 2, result[2]=6-2=4
              push 6                     stack=[6]         result=[1,1,4,2,1,1,0,0]
i=7, temp=73: 73<76, push 7              stack=[6,7]       result=[1,1,4,2,1,1,0,0]

Remaining in stack: indices 6 and 7, already initialized to 0.
Final: [1,1,4,2,1,1,0,0]

The key moment is at i=5 (temperature 72). In a single pass through the while loop it settles two open accounts — index 4 (temperature 69) and index 3 (temperature 71) — without revisiting any element. Brute force would have repeated those comparisons separately for each of indices 3 and 4.

Time: O(n). Each index is pushed exactly once and popped at most once. Total operations: 2n in the worst case, so the loop runs in O(n) regardless of how many pops happen inside the while.

Space: O(n). The stack holds at most all n indices — this happens when the array is strictly decreasing and nothing ever gets popped until the entire array has been scanned.

Approach 3: array-based optimization using bounded temperatures

The hint in the problem statement says: "if the temperature is 70 today, then a warmer temperature must be 71, 72, ..., 100. We could remember when all of them occur next." That is exactly what this approach does.

Instead of a stack, maintain an array next_warmer of size 101 where next_warmer[t] holds the most recently seen index with temperature t. You iterate right to left. At each index i with temperature t, you need the minimum index among all entries next_warmer[t+1] through next_warmer[100]. That minimum is the nearest future day that is warmer.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        result = [0] * n
        next_warmer = [float('inf')] * 101  # next_warmer[t] = nearest index with temperature t
 
        for i in range(n - 1, -1, -1):
            t = temperatures[i]
            # find the nearest index among all temperatures strictly warmer
            warmer_idx = min(next_warmer[t + 1:])
            if warmer_idx != float('inf'):
                result[i] = warmer_idx - i
            next_warmer[t] = i  # record that temperature t last appeared at index i
 
        return result

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        int n = temperatures.Length;
        int[] result = new int[n];
        int[] nextWarmer = new int[101];
        for (int t = 0; t <= 100; t++) nextWarmer[t] = int.MaxValue;
 
        for (int i = n - 1; i >= 0; i--) {
            int t = temperatures[i];
            int warmerIdx = int.MaxValue;
            for (int w = t + 1; w <= 100; w++) {
                if (nextWarmer[w] < warmerIdx) warmerIdx = nextWarmer[w];
            }
            if (warmerIdx != int.MaxValue) result[i] = warmerIdx - i;
            nextWarmer[t] = i;
        }
 
        return result;
    }
}

Time: O(71 * n). For each of the n elements, you scan at most 70 entries in next_warmer (temperatures 101 minus the current temperature, at most 70). That is still O(n) by complexity class — the 71 is a constant — but the constant is meaningful in practice.

Space: O(71) = O(1). The next_warmer array is bounded by the temperature range, not by n. This is the real advantage of this approach over the stack: the auxiliary structure does not grow with input size.

Edge cases in depth

Single-element array [50]: the outer loop in brute force runs zero times (range stops at n-1 = 0). The stack approach pushes index 0 and finishes; nothing is popped. The array approach's min over next_warmer[51:] is inf, so result[0] stays 0. All three return [0] correctly.

Strictly decreasing array [90, 80, 70, 60]: brute force does the maximum work — the inner loop never breaks early and runs 3 + 2 + 1 = 6 comparisons. The stack accumulates all four indices and nothing is ever popped. Result is [0, 0, 0, 0]. The array approach similarly finds no warmer day for any index.

Strictly increasing array [30, 40, 50, 60]: brute force's inner loop always breaks after one step. The stack pops the previous index immediately every time — it never grows beyond size 1. The array approach finds the immediate right neighbor for every index. Result: [1, 1, 1, 0].

Equal-temperature neighbors [70, 70, 71]: the condition is temperatures[i] > temperatures[stack[-1]], strict. Index 0 (temp 70) is pushed; index 1 (temp 70) does not trigger the pop because 70 > 70 is false. Both 0 and 1 are on the stack when index 2 (temp 71) arrives. Pop index 1: result[1] = 2 - 1 = 1. Pop index 0: result[0] = 2 - 0 = 2. Result: [2, 1, 0]. The strict inequality is load-bearing.

All identical temperatures [75, 75, 75]: no element ever triggers a pop. Stack ends with all three indices. Result: [0, 0, 0].

Comparison table

The bounded-array approach technically runs in O(1) space and O(n) time, which sounds optimal. In practice, it processes 71 comparisons per element versus an amortized average of 2 per element for the stack. For n = 10^5, the stack does roughly 200,000 total operations; the bounded array does 7,100,000. The stack wins on actual speed despite identical O-class.

The underlying pattern and what I would ship

This is the canonical "next greater element" pattern: find, for each index, the nearest future index where the value is strictly larger. The monotonic decreasing stack solves the entire family. The key insight — which shows up in Problems 496, 503, 901, and others — is that you store indices of unsettled elements in the stack, not the values themselves. When a new element arrives, it settles everything it outranks in a single while loop.

I would ship the monotonic stack. It is O(n) in both time and space, the code is short and readable, and it maps directly to the problem's structure: each day waits in the stack until it is resolved. The bounded-array approach is worth knowing because it demonstrates that the temperature constraint is exploitable, but in any real setting the 71x constant overhead makes it slower in practice.

The brute force is the right first answer to give in an interview before optimizing. Stating it and then explaining why it fails the constraint is better than jumping straight to the stack.

Where this sits in the stack series and what comes next

Daily Temperatures is the cleanest expression of the monotonic stack pattern. It strips away every complication — no circular wraparound, no two-array merge, no span calculation — and leaves just the core: a stack of pending indices resolved by incoming larger values.

Next Greater Element I (496) is the simplified warmup. Given two arrays, find the next greater element in the second array for each element in the first. The stack logic is identical; the extra step is building a hash map from value to answer. A good problem to try before this one.

Next Greater Element II (503) adds one twist: the array is circular, so you may need to wrap around. The standard trick is to iterate 2n times with index i % n. Everything else stays the same.

Online Stock Span (901) asks: for each incoming stock price, how many consecutive days going backward had a price <= today? It is the backward analog of this problem. A monotonic decreasing stack again, but now each entry carries a count, and when you pop you accumulate spans.

Largest Rectangle in Histogram (84) uses a monotonic increasing stack to find, for each bar, the nearest shorter bar on each side. The stack logic runs twice (once left-to-right, once right-to-left, or combined in one pass). If Daily Temperatures is comfortable, Histogram is the hard escalation that tests whether you genuinely own the pattern.