Daily Temperatures — Monotonic Stack Next Greater Element [LC 739]

Problem Statement#

Given an array temperatures, return an array answer where answer[i] is the number of days after day i until a warmer temperature. If no future day is warmer, answer[i] = 0.

Constraints:

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

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

Input:  temperatures = [30,40,50,60]
Output: [1,1,1,0]

Why This Problem Matters#

Daily Temperatures is the canonical introduction to the monotonic stack — one of the most valuable patterns in FAANG interviews. Amazon and Google use it directly; Meta and Microsoft use close variants. The brute-force O(n²) approach is trivially correct but times out at n = 10^5. The O(n) insight — a single warm day can resolve many waiting cooler days at once — is exactly the amortized thinking interviewers test.

Mastering this problem gives you the foundation for at least six others: Next Greater Element I and II (LC 496, 503), Online Stock Span (LC 901), Largest Rectangle in Histogram (LC 84), Maximal Rectangle (LC 85), and Trapping Rain Water (LC 42). All share the same "pop when the invariant breaks" structure.

The Core Insight#

Use a monotonic decreasing stack of indices. The stack always holds indices whose temperatures are decreasing from bottom to top — each index is "waiting" for a future warmer day.

When processing day i:

1. While the stack is non-empty and temperatures[i] > temperatures[stack.top()]: pop index j, set answer[j] = i - j
2. Push i onto the stack

After the full iteration, any index still in the stack never found a warmer day — its answer stays 0. Each index is pushed exactly once and popped at most once, making total work O(n) despite the nested while loop.

Visual Dry Run#

Input: [73, 74, 75, 71, 69, 72, 76, 73]

Indices 6 and 7 remain in stack — no warmer day found, answer stays 0. Final: [1,1,4,2,1,1,0,0]

Solution (Optimal)#

class Solution:
    def dailyTemperatures(self, temperatures):
        n = len(temperatures)
        answer = [0] * n
        stack = []  # monotonic decreasing stack of indices
        for i, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                j = stack.pop()
                answer[j] = i - j
            stack.append(i)
        return answer

var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);
    const stack = [];
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && temperatures[i] > temperatures[stack.at(-1)]) {
            const j = stack.pop();
            answer[j] = i - j;
        }
        stack.push(i);
    }
    return answer;
};

Time: O(n) — each index pushed and popped at most once Space: O(n) — stack can hold all indices in worst case (strictly descending input)

Common Mistakes#

• Storing temperatures in the stack instead of indices — you need the index to compute i - j
• Using a monotonic increasing stack — that finds "next cooler", not "next warmer"
• Using >= instead of > — strictly warmer is required; equal temperatures must not pop
• Returning -1 for days with no future warmer day — the problem requires 0
• Forgetting to initialize the answer array with zeros — remaining stack entries need 0

Interview Tips#

• State the key insight: "one warm day can resolve many waiting cooler days, so total work is O(n)"
• Clarify upfront: store indices not temperatures, because you need position to compute the wait
• Draw stack state for a short example step by step — interviewers love visual dry runs
• Explain amortized O(n): each element does at most one push and one pop across the whole algorithm
• Mention this pattern directly solves Next Greater Element, Online Stock Span, and Histogram Rectangle

Follow-up Questions#

• How would you solve this for a circular array — next greater wraps around? (Iterate 2n steps with i % n, LC 503)
• What if you want the previous warmer day instead of the next? (Iterate right to left with same stack logic)
• How does this generalize to "next smaller element"? (Use monotonic increasing stack, pop when current is smaller)
• Can you solve Online Stock Span using the same pattern? (Yes — monotonic decreasing stack of price-span pairs, LC 901)
• What is the worst-case space usage? (O(n) when input is strictly decreasing — every element waits forever)

Key Takeaways#

• LeetCode 739 is the canonical monotonic stack problem, asked at Amazon, Google, and Meta
• A monotonic decreasing stack of indices solves "next greater element" in O(n) amortized time
• Always store indices in the stack, not values — index gives both position and value via lookup
• Pop when current temperature exceeds stack top; current day is the answer for everything popped
• Each element is pushed once and popped at most once — O(n) total work despite the nested while loop
• Zero-initialized answer array handles remaining stack entries automatically — no post-processing needed
• Mastering LC 739 directly unlocks six other problems: LC 496, 503, 84, 85, 42, and 901