Daily Temperatures — Monotonic Stack Pattern

This is a Medium problem and the most common gateway to the monotonic stack pattern. Once you see how it works here, the same idea solves Next Greater Element, Stock Span, Largest Rectangle in Histogram, and more.

The Problem

Given an array temperatures of integers representing daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after day i 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]

Intuition

The brute force scans forward from each day until it finds a warmer one — O(n^2). On a strictly decreasing input the inner loop runs to the end every time. With n = 10^5 that is 10^10 operations.

The monotonic decreasing stack keeps indices of days that are still waiting for a warmer day. As we walk the array, any day on top of the stack that is colder than the current day finds its answer right now. Two invariants hold throughout the loop: the stack contains indices in increasing order, and the temperatures at those indices are non-increasing from bottom to top. Each index is pushed once and popped at most once, so the total work is O(n).

Explanation with Example

Take temperatures = [73, 74, 75, 71, 69, 72, 76, 73].

• i = 0, temp 73. Stack empty, push. Stack [0].
• i = 1, temp 74. Top is 73, colder. Pop 0, set answer[0] = 1. Push 1.
• i = 2, temp 75. Top is 74, colder. Pop 1, set answer[1] = 1. Push 2.
• i = 3, temp 71. Push. Stack [2, 3].
• i = 4, temp 69. Push. Stack [2, 3, 4].
• i = 5, temp 72. Pop 4 (answer[4] = 1), pop 3 (answer[3] = 2). Push 5. Stack [2, 5].
• i = 6, temp 76. Pop 5 (answer[5] = 1), pop 2 (answer[2] = 4). Push 6. Stack [6].
• i = 7, temp 73. Push. Stack [6, 7].

i=2  push 75   stack idx: [2]      temps: [75]
i=3  push 71   stack idx: [2,3]    temps: [75,71]
i=4  push 69   stack idx: [2,3,4]  temps: [75,71,69]
i=5  temp 72 > 69 pop 4 ans[4]=1
            72 > 71 pop 3 ans[3]=2
            72 < 75 stop, push 5
            stack idx: [2,5]    temps: [75,72]
i=6  temp 76 pops 5 then 2  -> ans[2]=4

Indices 6 and 7 remain on the stack at the end. They never found a warmer day, so their answer stays 0. Final: [1, 1, 4, 2, 1, 1, 0, 0].

Code

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []  # indices, temperatures at these indices are decreasing
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        return answer;
    }
}

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> answer(n, 0);
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
                int j = st.top(); st.pop();
                answer[j] = i - j;
            }
            st.push(i);
        }
        return answer;
    }
};

Edge Cases

• Empty array: return an empty array.
• Single element: return [0].
• Strictly increasing input: each day pops the previous one and sets the answer to 1.
• Strictly decreasing input: nothing is ever popped during the loop.
• All equal temperatures: nothing is ever strictly warmer, so every answer is 0. The strict < matters here. Using <= would be incorrect.
• Very large arrays: O(n) handles 10^5 instantly.

Complexity Analysis

• Time: O(n) amortized. Each index is pushed once and popped at most once.
• Space: O(n) for the answer and up to O(n) for the stack.

See Big O notation refresher for the amortization accounting.

How to Explain It in an Interview

• Restate the problem as next greater element with the answer being the distance, not the value.
• Mention the quadratic brute force and its failure mode.
• Introduce the monotonic stack and state both invariants out loud.
• Walk through the push and pop rules in one sentence each.
• Justify the linear time by amortization.

Naming the pattern buys you credibility because interviewers know the family of problems it unlocks.

Related Problems

• Next Greater Element I, the value-returning version.
• Next Greater Element II, circular array variant.
• Largest Rectangle in Histogram, the hardest classic in this family.
• Online Stock Span, which uses the same stack with a count.

For the underlying structure, revisit stacks and queues.

Wrap up

Keep indices on a stack, pop them when the current value beats them, and let amortized analysis give you a linear time bound. Once you internalize this template, a bucket of problems collapses into a small variation of the same loop.