Daily Temperatures — Monotonic Stack With Index Distances

Problem Statement#

Given an array of integers temperatures, return an array answer where answer[i] is the number of days you must wait after day i to get a warmer temperature. If no warmer day exists, answer[i] is 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 medium monotonic stack problem and one of the most frequently asked in FAANG phone screens. Amazon, Google, and Meta all use it or near-identical variants as a screening question. It is rated medium because it requires the additional insight of storing indices in the stack — not the values themselves — so that you can compute the distance (i - stack[-1]) when you pop.

This problem is the bridge between Next Greater Element I (easy, store values) and harder stack problems like Largest Rectangle in Histogram (hard, store indices to compute width). Mastering Daily Temperatures means you understand both the concept and the index-based implementation detail that unlocks the harder problems.

The temperature range is small (30–100), which hints at a possible frequency-array optimization. In an interview, mention this observation but lead with the clean monotonic stack solution.

The Core Insight#

For each day, you want to know: how many days until a strictly warmer temperature?

The brute force is O(n²): scan right from each day until finding a warmer day. With n = 10^5, this TLEs.

The monotonic stack insight: process days left to right, maintaining a stack of day indices whose temperatures are still looking for a warmer future day. The stack temperatures are always in non-increasing order. When day i has a temperature warmer than the stack top, that index found its answer — pop it and compute answer[popped] = i - popped.

The critical upgrade from Next Greater Element I: store indices, not values, so you can compute the gap.

Visual Dry Run#

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

After loop, stack=[6,7] → ans[6]=0, ans[7]=0. Result: [1,1,4,2,1,1,0,0].

Solution (Optimal)#

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = []  # Stack of indices, decreasing temperature order
 
        for i, temp in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < temp:
                prev_day = stack.pop()
                answer[prev_day] = i - prev_day
            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[stack[stack.length - 1]] < temperatures[i]) {
            const prevDay = stack.pop();
            answer[prevDay] = i - prevDay;
        }
        stack.push(i);
    }
 
    return answer;
};

Time: O(n) — each index is pushed once and popped at most once; total stack operations are 2n Space: O(n) — stack holds at most n indices in the worst case (strictly decreasing temperatures)

Common Mistakes#

• Storing temperatures instead of indices in the stack — you lose the ability to compute the distance
• Using a non-strict comparison (<= instead of <) — equal temperatures should not resolve each other; the problem requires strictly warmer
• Forgetting to initialize the answer array to zeros — remaining stack elements (no warmer day) need 0, which initialization handles automatically without post-loop cleanup
• Popping with the wrong condition — temperatures[stack[-1]] < temperatures[i] pops when today is warmer; flipping it produces the next cooler element

Interview Tips#

• Mention the index-storage distinction early: "I maintain a stack of day indices in decreasing temperature order. When a warmer day arrives, I pop and compute current_index - popped_index."
• Explain amortized complexity: "Each index is pushed once and popped at most once, giving 2n stack operations total across n iterations — O(n) amortized."
• If asked about the small temperature range (30–100), describe the optimization: scan backwards and use a 101-slot array to track the nearest index of each temperature value. Mention it as an alternative but implement the stack solution.

Follow-up Questions#

• What if you want the previous warmer day? Process right to left, or maintain a stack tracking left-side context for each element.
• What if you want the next day in a temperature range [lo, hi]? A monotonic stack no longer applies directly; this becomes a range-query problem needing a segment tree.
• Can you solve this with a backward scan? Yes: process right to left and jump forward using precomputed answers. O(n) in practice but O(n²) worst case — the monotonic stack is strictly O(n).
• How does this relate to Largest Rectangle in Histogram? Both store indices; in histogram you compute widths using the index difference, just like computing day distances here.

Key Takeaways#

• Store indices in the stack, not values — compare via temperatures[stack[-1]] and compute distance via i - stack[-1].
• The decreasing temperature invariant means each index is pushed and popped exactly once, giving O(n) amortized time.
• Initialize the answer array to 0 so remaining stack elements are handled automatically without extra post-loop code.
• This index-distance pattern is the backbone of every harder monotonic stack problem including Largest Rectangle in Histogram.
• The key upgrade from Next Greater Element I to Daily Temperatures is switching from value-based to index-based stack storage.
• Use strict < comparison — equal temperatures should not resolve each other since the problem requires strictly warmer days.
• Daily Temperatures is the most important medium monotonic stack problem to master before tackling hard-level stack problems.