Coding interview problems › Stack & Monotonic Stack

📚 Stack & Monotonic Stack Medium

Daily Temperatures

Daily Temperatures explained with a monotonic stack: waiting days pop the moment a warmer day arrives, giving O(n). Tested Python, pitfalls and a live visual.

Also searched as: days until a warmer temperature · next warmer day · monotonic stack problems

📚

Try it live Free

Stacks & the Monotonic Stack

Switch to the monotonic stack mode on Daily Temperatures and watch waiting days pop the instant a warmer one arrives, each pop filling in one answer.

Open the playground →

The problem

Given a list of daily temperatures, return a list where entry i is the number of days you must wait after day i for a warmer day. If no warmer day ever comes, use 0.

Inputtemps = [30, 32, 31, 29, 35, 30]
Output[1, 3, 2, 1, 0, 0]

Day 2 (31) waits until day 4 (35).

The key insight

Keep a stack of the days that are still waiting for a warmer day. Their temperatures are decreasing from bottom to top, otherwise one of them would already have been answered. When a new day arrives, it answers every waiting day on top that is colder than it: pop them and record the gap, then push the new day.

Brute force first: For each day, scanning forward until a warmer day appears works but takes O(n²) on a falling sequence of temperatures.

Step-by-step approach

  1. Create answer = [0] * n and an empty stack of indices.
  2. For each day i with temperature t:
  3. While the stack is not empty and temps[stack[-1]] < t, pop index j and set answer[j] = i - j.
  4. Push i; it now waits for its own warmer day.
  5. Days left on the stack at the end never see a warmer day and keep their 0.

Python solution

PYTHON 3tested
def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []                              # indices waiting for a warmer day
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j               # day i is j's first warmer day
        stack.append(i)
    return answer

Complexity

TimeO(n)
SpaceO(n)

Every index is pushed once and popped at most once, so the inner while loop does O(n) work in total across the whole scan, not per day.

Common mistakes

Frequently asked questions

What is the time and space complexity of Daily Temperatures?

O(n) time, because each index is pushed and popped at most once, and O(n) space for the stack and the answer.

Why is it called a monotonic stack?

The temperatures of the indices on the stack are always in decreasing order from bottom to top. Keeping that order is what lets one comparison with the top settle many days at once.

Can I solve it from right to left instead?

Yes. Scan backwards, pop every index whose temperature is not warmer than today, and the top of the stack, if any, is the next warmer day. It is the same O(n) idea.

Which other problems use this pattern?

Next Greater Element, Online Stock Span, Largest Rectangle in Histogram and Trapping Rain Water all use a monotonic stack.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Stack & Monotonic Stack Stacks & the Monotonic Stack lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.