Daily Temperatures

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Related Problems
Key Takeaways

📋 Problem Statement

Given an array temperatures, build an output array where answer[i] is the number of days until a warmer temperature after day i.

Examples

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

Example 2:
Input: [30,40,50,60]
Output: [1,1,1,0]

Example 3:
Input: [30,60,90]
Output: [1,1,0]

Constraints

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

🎯 Real-World Analogy

Pending Questions Queue

Think of each day as asking: "When do I get a warmer day?" Some questions stay unresolved until a future day arrives that can answer them.

A monotonic stack stores unresolved day indices in decreasing temperature order. When a warmer day appears, it resolves one or more pending days on top of the stack.

💡 Key Insights

Store indices, not values, so you can compute day distance.
Maintain a stack of decreasing temperatures by index.
When current temp is warmer than stack top, pop and resolve answers.
Each index is pushed once and popped at most once.
Unresolved indices left in stack naturally remain 0.

💻 Solution Approaches

Approach 1: Brute Force

Time: O(N²) | Space: O(1)

For each day, scan forward until finding a warmer day. Straightforward but too slow for large inputs.

Approach 2: Monotonic Decreasing Stack (Recommended)

Time: O(N) | Space: O(N)

Track unresolved days in a stack. Resolve them in batches when a warmer temperature arrives.

Python Implementation

          from typing import List


def daily_temperatures(temperatures: List[int]) -> List[int]:
    """
    Monotonic decreasing stack of indices.

    Time: O(N)
    Space: O(N)
    """
    n = len(temperatures)
    answer = [0] * n
    stack = []  # indices with unresolved warmer day

    for i, current in enumerate(temperatures):
        # Resolve all previous colder days.
        while stack and temperatures[stack[-1]] < current:
            prev = stack.pop()
            answer[prev] = i - prev

        stack.append(i)

    return answer
        

JavaScript Implementation

          function dailyTemperatures(temperatures) {
  /**
   * Monotonic decreasing stack of indices.
   *
   * Time: O(N)
   * Space: O(N)
   */
  const n = temperatures.length;
  const answer = new Array(n).fill(0);
  const stack = []; // unresolved indices

  for (let i = 0; i < n; i++) {
    const current = temperatures[i];

    // Resolve all previous colder days.
    while (stack.length > 0 && temperatures[stack[stack.length - 1]] < current) {
      const prev = stack.pop();
      answer[prev] = i - prev;
    }

    stack.push(i);
  }

  return answer;
}
        

🔍 Step-by-Step Walkthrough

Trace [73,74,75,71,69,72,76,73]:

            Day 0 (73): stack = [0]
          
            Day 1 (74): 74 > 73 so resolve day 0 -> answer[0] = 1. stack = [1]
          
            Day 2 (75): 75 > 74 so resolve day 1 -> answer[1] = 1. stack = [2]
          
            Day 5 (72): resolves day 4 (69) and day 3 (71). answer[4]=1, answer[3]=2
          
            Day 6 (76): resolves day 5 and day 2.
            Final answer: [1,1,4,2,1,1,0,0]

⚡ Complexity Analysis

Time Complexity: O(N)

Each index is pushed once.
Each index is popped at most once.
Total stack operations are linear.

Space Complexity: O(N)

Output array: O(N).
Stack: worst-case O(N) for decreasing temperatures.

🔧 Edge Cases

Single day -> always [0]
Strictly decreasing temperatures -> all zeros
Strictly increasing temperatures -> mostly ones, last zero
Repeated temperatures should not pop on equality
Large arrays near upper bound must remain O(N)

🧪 Test Cases

Python

          def test_daily_temperatures():
    assert daily_temperatures([73,74,75,71,69,72,76,73]) == [1,1,4,2,1,1,0,0]
    assert daily_temperatures([30,40,50,60]) == [1,1,1,0]
    assert daily_temperatures([30,60,90]) == [1,1,0]
    assert daily_temperatures([90,80,70]) == [0,0,0]
    assert daily_temperatures([70]) == [0]

    print("✅ all tests passed")
        

JavaScript

          function testDailyTemperatures() {
  console.assert(
    JSON.stringify(dailyTemperatures([73,74,75,71,69,72,76,73])) ===
      JSON.stringify([1,1,4,2,1,1,0,0]),
    "test 1"
  );
  console.assert(
    JSON.stringify(dailyTemperatures([30,40,50,60])) ===
      JSON.stringify([1,1,1,0]),
    "test 2"
  );
  console.assert(
    JSON.stringify(dailyTemperatures([90,80,70])) ===
      JSON.stringify([0,0,0]),
    "test 3"
  );

  console.log("✅ all tests passed");
}
        

💼 Interview Tips

Say "monotonic decreasing stack of indices" explicitly.
Explain why indices are needed to compute waiting days.
Use strict comparison <, not <=, for warmer day logic.
Call out push-once/pop-once argument for O(N).
Mention this template applies to next greater element variants.

🎓 Key Takeaways

Monotonic stacks solve "next greater" queries efficiently.
Store unresolved indices and resolve in bursts when a better value appears.
Index-based stack gives both correctness and linear performance.

← Back to All Algorithms