Daily Temperatures: Monotonic Stack Explained

LeetCode's Daily Temperatures is the best introduction to monotonic stacks. It is rated medium, and once you see the pattern, you will recognize it everywhere. The problem is simple to state, the brute force is obvious, and the optimal solution is a clean single-pass algorithm that cuts the time from O(n^2) to O(n).

The problem

You are given an array of daily temperatures. For each day, return how many days you have to wait until a warmer temperature. If there is no future day with a warmer temperature, put 0 for that day.

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

Day 0 is 73 degrees. Day 1 is 74, which is warmer, so the answer for day 0 is 1. Day 2 is 75, and the next warmer day is day 6 (76 degrees), which is 4 days later. Days 6 and 7 have no warmer day after them, so their answers are 0.

The brute force

The straightforward approach: for each day, scan forward through the rest of the array until you find a warmer temperature.

def daily_temperatures_brute(temps):
    n = len(temps)
    result = [0] * n

    for i in range(n):
        for j in range(i + 1, n):
            if temps[j] > temps[i]:
                result[i] = j - i
                break

    return result

This works, but the inner loop can scan up to n elements for each of the n days. That is O(n^2) in the worst case (for example, a sorted descending array). For 100,000 temperatures, that is too slow.

The problem with brute force is that it throws away information. When you scan forward from day 3, you learn things about days 4, 5, 6, but you do not remember any of it when you start scanning from day 4.

The key insight: use a stack

Here is the idea. Instead of scanning forward from each day, walk through the array once from left to right. Keep a stack of days that are "waiting" for a warmer temperature.

When you reach a new day, check: is today warmer than the day on top of the stack? If yes, that waiting day just found its answer. Pop it and record the distance. Keep popping as long as the current temperature is warmer than the stack's top.

Then push the current day onto the stack, because it too is now waiting for a warmer day.

Why does this work? The stack naturally maintains a decreasing order of temperatures (from bottom to top). Every time you encounter a temperature that breaks this pattern (it is warmer than the top), you resolve all the days that were waiting. Each day gets pushed once and popped once, so the total work is O(n).

Step-by-step walkthrough

Let's trace through temps = [73, 74, 75, 71, 69, 72, 76, 73]. The array is shown on the left with the current index highlighted. The stack is on the right. Green numbers below the array are the answers filled in so far.

Notice a few things:

• The stack is always decreasing. Every time we push, the new value is less than or equal to whatever is already on top. That is what makes it a monotonic (decreasing) stack.
• Each index gets pushed once and popped at most once. That is why the total time is O(n), even though some steps pop multiple elements.
• Step 6 is the interesting one. Temperature 72 pops two elements (69 and 71) because it is warmer than both. This is where the stack saves you from redundant scanning.
• Step 7 is even more dramatic. Temperature 76 clears the whole stack, resolving the answer for index 2 which had been waiting since step 3.

The code

def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []  # stores indices of days waiting for warmer

    for i in range(n):
        # Pop all days that are colder than today
        while stack and temps[i] > temps[stack[-1]]:
            prev = stack.pop()
            result[prev] = i - prev

        stack.append(i)

    return result

That is 10 lines of logic. Let's break it down:

1. Initialize result to all zeros. Days that never find a warmer temperature keep their default 0.
2. Walk through each day left to right.
3. While the stack is not empty and today is warmer than the top: pop the top index and record the answer as i - prev.
4. Push the current index. It is now waiting for its own warmer day.
5. When the loop ends, anything left on the stack has no warmer day, and the answer is already 0.

The while loop is the heart of it. It can pop multiple elements in a single iteration of the outer for loop, but across the entire algorithm, each index is pushed and popped at most once. That is the key to the O(n) guarantee.

Complexity analysis

Time: O(n). Each of the n indices is pushed onto the stack exactly once and popped at most once. The while loop does at most n pops total across all iterations of the for loop. So the total work is O(n).

Space: O(n). In the worst case (a strictly decreasing array like [100, 99, 98, ...]), every index gets pushed and none get popped until the end. The stack holds all n elements.

You trade O(n) space for an O(n) time improvement. That is almost always worth it.

Common mistakes

A few things to watch for when implementing this:

1. Using >= instead of > in the while condition. The problem asks for a warmer temperature, meaning strictly greater. If you pop on equal temperatures, you will give incorrect answers for days that have the same temperature as a later day.

2. Storing temperatures instead of indices. You need the index to compute the number of days. Always push the index and look up the temperature with temps[stack[-1]].

3. Forgetting to check if stack before accessing stack[-1]. The while loop handles this with stack and ..., but if you restructure the code, an empty stack access will crash.

4. Iterating right to left. The "next greater element" template from many tutorials goes right to left. Daily Temperatures works naturally left to right, which is more intuitive for this specific problem. Both directions are valid, but mixing them up leads to bugs.

Why this is a "next greater element" problem

Daily Temperatures is a specific instance of the general Next Greater Element pattern. For each element in an array, find the nearest element to its right that is strictly greater. The only twist here is that you return the distance rather than the value itself.

The same monotonic stack technique solves:

• Next Greater Element I/II (LeetCode 496, 503): find the next greater value directly, including circular arrays
• Largest Rectangle in Histogram (LeetCode 84): track the next/previous smaller bar to compute widths
• Stock Span Problem: how many consecutive preceding days had a price less than or equal to today
• Trapping Rain Water (stack approach): use a monotonic stack to find bounding walls

Once you internalize the pop-when-greater loop, all of these problems become variations on the same theme.

The building blocks

This problem is built on a single reusable brick:

Monotonic stack pop loop

The core pattern is:

while stack and compare(current, stack[-1]):
    popped = stack.pop()
    # process popped element using current
stack.append(current)

This is the building block. The only things that change between problems are:

• What you compare (greater, less, greater-or-equal)
• What you store (index, value, tuple of both)
• What you compute when popping (distance, area, water volume)

For Daily Temperatures, the comparison is temps[i] > temps[stack[-1]], you store indices, and you compute i - prev. For Largest Rectangle in Histogram, the comparison is heights[i] < heights[stack[-1]], and you compute areas. Same brick, different wall.

Edge cases

Before submitting, verify your solution handles:

• All the same temperature like [72, 72, 72, 72]: every answer is 0. Nothing gets popped because equal is not greater.
• Strictly increasing like [60, 70, 80, 90]: each day's answer is 1. Every push triggers an immediate pop of the previous day.
• Strictly decreasing like [90, 80, 70, 60]: every answer is 0. Nothing gets popped. Stack grows to n elements.
• Single element [50]: answer is [0].
• Two elements [50, 60]: answer is [1, 0]. [60, 50]: answer is [0, 0].

The monotonic stack solution handles all of these without special cases.

From understanding to recall

You have read through the monotonic stack solution. You see how the pop loop works and why it is O(n). But can you write it cold in an interview three weeks from now?

That is the real challenge. The pattern is not complicated, but it has a few moving parts: the while loop condition, pushing indices, computing the distance on pop. Under time pressure, people mix up the comparison direction, forget to push after the while loop, or store values instead of indices. These are not conceptual mistakes. They are recall mistakes.

Spaced repetition is built for exactly this. Instead of solving Daily Temperatures once and moving on, you practice the monotonic stack pop loop at increasing intervals. Each time, you write it from scratch. After a few repetitions, it is in your long-term memory and you can apply it to any next-greater-element variant without thinking twice.

Related posts

• Stack Patterns: Matching, Nesting, and More - The full overview of stack patterns, including monotonic stacks and bracket matching
• Trapping Rain Water - Uses the same "find bounding elements" idea, though the optimal solution uses two pointers instead of a stack
• Valid Parentheses - The classic stack problem for bracket matching, a simpler entry point into stack-based thinking

CodeBricks breaks the monotonic stack pattern into its reusable pieces and drills them individually. You type the pop loop from scratch each time, building the muscle memory so that when you see Daily Temperatures or Next Greater Element in an interview, the code flows without hesitation.