Daily Temperatures: Monotonic stack Pattern

Learning Outcome

After this lesson, you should be able to use a monotonic stack to resolve "next greater" style questions in one pass.

Problem Statement

Given daily temperatures, return an array where each value tells how many days you must wait for a warmer temperature. If there is no future warmer day, use 0.

Brute Force Approach

For each day, scan all later days until a warmer temperature is found.

This is clear, but in the worst case it costs O(n^2).

Optimized Approach

Keep a stack of indices whose warmer day has not been found yet. The stack is decreasing by temperature. When the current temperature is warmer than the temperature at the stack top, pop that index and fill its answer.

Exact Pseudocode

answer = array of zeroes
stack = empty stack of indices
for i from 0 to length(temperatures) - 1:
  while stack is not empty and temperatures[i] > temperatures[stack.top]:
    prev = pop stack
    answer[prev] = i - prev
  push i
return answer
  

Reference Code

class Solution:
    def dailyTemperatures(self, temperatures):
        answer = [0] * len(temperatures)
        stack = []

        for i, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                prev = stack.pop()
                answer[prev] = i - prev
            stack.append(i)

        return answer
  

Sample Dry Run

Complexity

Edge Cases

• Strictly decreasing temperatures produce all zeroes.
• Equal temperatures are not warmer.
• Single-day input returns [0].

Interview Checklist

• Store indices, not temperatures, so you can compute distance.
• Use >, not >=, because equal is not warmer.
• Leave unresolved days as zero.

FAQs