LeetCode Daily Temperatures: Monotonic Stack Pattern

LeetCode 739, Daily Temperatures, is a Medium problem and the most common gateway to the monotonic stack pattern. Once you see how it works on this question, the same idea solves Next Greater Element, Stock Span, Largest Rectangle in Histogram, and more. We will go from the brute force to the optimal O(n) solution and explain why the stack stays small even though we iterate the whole array.

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]

The constraint is typically up to 10^5 days, with temperatures in a small range.

Brute Force

For each day, scan forward until we find a strictly warmer day.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i
                break
    return answer

In the worst case, like a strictly decreasing input, the inner loop runs to the end each time. Time is O(n^2). With n = 10^5 that is 10^10 operations and a guaranteed timeout.

Optimal Solution

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.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []  # stores 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

Two invariants hold throughout:

• The stack contains indices in increasing order.
• The temperatures at those indices are non-increasing from bottom to top.

When the current temperature is warmer than the one on top of the stack, that index gets its answer. We keep popping until the stack is empty or the top is no longer colder. Each index is pushed once and popped at most once, so the total work across the loop is O(n) even though it has an inner while.

Walk Through an Example

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

• i = 0, temp 73. Stack is empty, push. Stack [0].
• i = 1, temp 74. Top is index 0 with 73, which is colder. Pop 0, set answer[0] = 1. Push 1. Stack [1].
• i = 2, temp 75. Top is index 1 with 74, colder. Pop 1, set answer[1] = 1. Push 2. Stack [2].
• i = 3, temp 71. Not warmer than top. Push 3. Stack [2, 3].
• i = 4, temp 69. Not warmer than top. Push 4. Stack [2, 3, 4].
• i = 5, temp 72. Top is index 4 with 69, colder. Pop 4, set answer[4] = 1. Top is index 3 with 71, colder. Pop 3, set answer[3] = 2. Top is index 2 with 75, not colder. Push 5. Stack [2, 5].
• i = 6, temp 76. Top is index 5 with 72, colder. Pop 5, set answer[5] = 1. Top is index 2 with 75, colder. Pop 2, set answer[2] = 4. Push 6. Stack [6].
• i = 7, temp 73. Not warmer than top. Push 7. Stack [6, 7].

After the loop the stack still contains [6, 7]. Those indices never found a warmer day, and their answer entries stay at the initial 0. The final array is [1, 1, 4, 2, 1, 1, 0, 0], which matches the expected output.

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. The stack ends up with every index and every answer stays 0.
• All equal temperatures: nothing is ever strictly warmer, so every answer is 0. The strict < in the while condition matters here. Using <= would be incorrect.
• Very large arrays: the algorithm is O(n), so 10^5 inputs run instantly.

Complexity Analysis

• Time: O(n) amortized. The inner while looks dangerous but each index is pushed once and popped at most once, so the total inner-loop work across the whole outer loop is bounded by n.
• Space: O(n) for the answer array and up to O(n) for the stack in the worst case, such as a strictly decreasing input.

If amortized analysis is unfamiliar, the Big O notation refresher goes through the 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 the failure mode on long decreasing runs.
• 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 the amortization argument: each index moves in and out of the stack once.

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

Related Problems

• LeetCode 496, Next Greater Element I, the value-returning version of this problem.
• LeetCode 503, Next Greater Element II, which handles a circular array.
• LeetCode 84, Largest Rectangle in Histogram, the hardest classic in this family.
• LeetCode 901, Online Stock Span, which uses the same stack with a count.

For the underlying structure, revisit stacks and queues. When you start composing this pattern with frequency counts, hashing and hash maps becomes a natural partner.

Wrap up

Daily Temperatures is the cleanest possible introduction to the monotonic stack. 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 the pattern here, an entire bucket of LeetCode problems collapses into a small variation of the same loop, which is exactly the kind of leverage interviews are designed to reward.