Daily Temperatures — Monotonic Decreasing Stack Explained

Problem Statement#

Given an array of integers temperatures representing daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day with a warmer temperature, keep 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]
Explanation:
Day 0 (73): next warmer is day 1 (74) → 1 day
Day 1 (74): next warmer is day 2 (75) → 1 day
Day 2 (75): next warmer is day 6 (76) → 4 days
Day 3 (71): next warmer is day 5 (72) → 2 days

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

Input:  temperatures = [30,60,90]
Output: [2,1,0]

Why This Problem Matters#

LC 739 is the canonical monotonic stack problem. Every list of "must-know stack problems" includes Daily Temperatures because:

1. It introduces the monotonic stack technique that solves 20+ LeetCode problems.
2. It demonstrates the "pending work" pattern: stack stores indices of days still waiting for their answer.
3. It is asked at Google, Amazon, Meta, Microsoft, and Bloomberg in both phone screens and on-site rounds.

The monotonic stack insight generalizes to: Next Greater Element (LC 496, 503), Online Stock Span (LC 901), Sum of Subarray Minimums (LC 907), Largest Rectangle in Histogram (LC 84), and Trapping Rain Water (LC 42). Master this problem and the harder ones become straightforward.

The Core Insight#

Naive approach: For each day i, scan forward to find the next warmer day. O(n^2) time.

Monotonic stack approach: Maintain a stack of indices of days whose answers are still unknown (waiting for a warmer day). Keep the stack in monotonically decreasing order of temperatures — whenever a new day i with temperature T[i] arrives, it resolves all pending days on the stack whose temperature is less than T[i].

Why decreasing order? Each element in the stack is a day that has not yet seen a warmer day. When we process day i, if it is warmer than the stack top, the stack top's answer is i - stack.top. We keep popping until we find a day warmer than day i (or exhaust the stack). Then push i as a new pending day.

The total number of push and pop operations is O(n) — each index is pushed once and popped at most once. That is O(n) overall.

Visual Dry Run#

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

Remaining stack [6,7]: no warmer day → ans[6]=ans[7]=0.

Result: [1,1,4,2,1,1,0,0]

Solution (Optimal)#

# Python — monotonic decreasing stack, O(n) time and space
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    # Stack stores INDICES of days still waiting for a warmer temperature
    # Invariant: temperatures at stack indices are monotonically decreasing
    stack = []
 
    for i in range(n):
        # While stack is not empty and current day is warmer than stack top day
        while stack and temperatures[stack[-1]] < temperatures[i]:
            prev_day = stack.pop()
            answer[prev_day] = i - prev_day  # days waited = current index - previous index
 
        stack.append(i)  # push current day as pending (no warmer day seen yet)
 
    # Remaining stack indices have no warmer day → answer stays 0
    return answer

// JavaScript — monotonic decreasing stack, O(n) time and space
function dailyTemperatures(temperatures) {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);
    const stack = [];  // stores indices of pending days
 
    for (let i = 0; i < n; i++) {
        // Resolve all pending days cooler than today
        while (stack.length > 0 && temperatures[stack[stack.length - 1]] < temperatures[i]) {
            const prevDay = stack.pop();
            answer[prevDay] = i - prevDay;
        }
        stack.push(i);
    }
 
    return answer;
}

Complexity:

Common Mistakes#

1. Storing temperatures instead of indices. The answer requires i - prev_day, so you must store indices, not temperature values. Storing temperatures loses the position information needed to compute the day difference.

2. Using greater-than-or-equal comparison. The problem asks for a strictly warmer day (>), not equal-or-warmer (>=). Using >= would incorrectly resolve days when temperatures are equal.

3. Popping without saving the index. When you pop the stack top, you need to compute i - prev_day. If you pop without saving prev = stack.pop(), you cannot compute the answer.

4. Not initializing the answer array with zeros. Remaining stack elements after the loop should have answer 0 — which is the default if you initialize answer = [0] * n. If you forget initialization, the remaining elements may have garbage values.

5. Using a list in JavaScript without proper bounds checking. stack[stack.length - 1] is undefined when the stack is empty. Always check stack.length > 0 before accessing the top.

Interview Tips#

• Describe the invariant clearly: "The stack holds indices of days in decreasing order of temperature. Each is waiting for a warmer future day."
• State the O(n) argument: "Each index is pushed exactly once and popped at most once. Total push+pop operations is at most 2n → O(n)."
• When asked why to store indices and not temperatures: "I need to compute the day difference i - prev_day, so I need the indices, not the values."
• Compare with the next greater element (LC 496): "Same pattern — the only difference is we compute index differences instead of returning the greater values."

Follow-up Questions#

1. Next Greater Element I (LC 496) — same pattern applied to elements instead of day differences.
2. Next Greater Element II (LC 503) — circular array; process the array twice (or use modulo indexing) with the same stack.
3. Online Stock Span (LC 901) — count consecutive days with stock prices less than or equal to today; same decreasing stack logic.
4. Largest Rectangle in Histogram (LC 84) — find the next smaller elements on both sides using two monotonic stacks.
5. Trapping Rain Water (LC 42) — use a monotonic stack to compute trapped water between bars.

Key Takeaways#

• A monotonic decreasing stack stores indices of elements waiting for their "next greater element" — whenever a larger element arrives, it resolves all pending smaller elements.
• Store indices, not values — you need index differences to compute how many days waited.
• Each element is pushed and popped at most once → O(n) total time despite the nested while loop.
• Elements remaining in the stack after the loop have no warmer future day → their answers remain 0.
• This is the foundational monotonic stack pattern — mastering it unlocks Next Greater Element (LC 496, 503), Stock Span (LC 901), Sum of Subarray Minimums (LC 907), Histogram (LC 84), and Trapping Rain Water (LC 42).
• In interviews, state the monotonic invariant and the amortized O(n) complexity argument before coding — this demonstrates deep understanding of the pattern.