Daily Temperatures

Find the number of days until a warmer temperature for each day.

Language Selection

Choose your preferred programming language

Showing: Python

Daily Temperatures

Problem Statement

Given an array of integers temperatures representing the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Examples

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Explanation: 
- Day 0: 73°F, next warmer day is day 1 (74°F) → 1 day
- Day 1: 74°F, next warmer day is day 2 (75°F) → 1 day
- Day 2: 75°F, next warmer day is day 6 (76°F) → 4 days
- Day 3: 71°F, next warmer day is day 5 (72°F) → 2 days
- Day 4: 69°F, next warmer day is day 5 (72°F) → 1 day
- Day 5: 72°F, next warmer day is day 6 (76°F) → 1 day
- Day 6: 76°F, no warmer day → 0 days
- Day 7: 73°F, no warmer day → 0 days

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Explanation: Each day has exactly one warmer day following it.

Constraints

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

Approach 1: Monotonic Stack (Optimal)

Algorithm

Use a monotonic stack to keep track of indices of temperatures in decreasing order. When we find a warmer temperature, we can calculate the days for all previous temperatures.

Steps:

  1. Use a stack to store indices of temperatures
  2. For each temperature, while stack is not empty and current temperature > stack top temperature:
    • Pop the index from stack
    • Calculate days = current index - popped index
    • Store the result
  3. Push current index to stack
  4. Return the result array

Implementation

Python:

def dailyTemperatures(temperatures):
    """
    Find days until warmer temperature using monotonic stack
    Time: O(n)
    Space: O(n)
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # Stack to store indices
    
    for i in range(n):
        # While stack is not empty and current temperature > stack top temperature
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index
        
        stack.append(i)
    
    return result

Java:

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            // While stack is not empty and current temperature > stack top temperature
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                result[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        
        return result;
    }
}

Go:

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    result := make([]int, n)
    stack := make([]int, 0)
    
    for i := 0; i < n; i++ {
        // While stack is not empty and current temperature > stack top temperature
        for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
            prevIndex := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[prevIndex] = i - prevIndex
        }
        stack = append(stack, i)
    }
    
    return result
}

JavaScript:

function dailyTemperatures(temperatures) {
    const n = temperatures.length;
    const result = new Array(n).fill(0);
    const stack = [];
    
    for (let i = 0; i < n; i++) {
        // While stack is not empty and current temperature > stack top temperature
        while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    
    return result;
}

C#:

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        int n = temperatures.Length;
        int[] result = new int[n];
        var stack = new Stack<int>();
        
        for (int i = 0; i < n; i++) {
            // While stack is not empty and current temperature > stack top temperature
            while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()]) {
                int prevIndex = stack.Pop();
                result[prevIndex] = i - prevIndex;
            }
            stack.Push(i);
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Each element is pushed and popped at most once
  • Space Complexity: O(n) - For the stack and result array

Approach 2: Brute Force

Algorithm

For each day, find the next warmer day by scanning forward.

Steps:

  1. For each day i, scan from i+1 to end
  2. Find the first day with higher temperature
  3. Calculate the difference in days
  4. Return the result array

Implementation

Python:

def dailyTemperaturesBruteForce(temperatures):
    """
    Find days until warmer temperature using brute force
    Time: O(n^2)
    Space: O(1) excluding output
    """
    n = len(temperatures)
    result = [0] * n
    
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                result[i] = j - i
                break
    
    return result

Java:

class Solution {
    public int[] dailyTemperaturesBruteForce(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    result[i] = j - i;
                    break;
                }
            }
        }
        
        return result;
    }
}

Go:

func dailyTemperaturesBruteForce(temperatures []int) []int {
    n := len(temperatures)
    result := make([]int, n)
    
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if temperatures[j] > temperatures[i] {
                result[i] = j - i
                break
            }
        }
    }
    
    return result
}

JavaScript:

function dailyTemperaturesBruteForce(temperatures) {
    const n = temperatures.length;
    const result = new Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (temperatures[j] > temperatures[i]) {
                result[i] = j - i;
                break;
            }
        }
    }
    
    return result;
}

C#:

public class Solution {
    public int[] DailyTemperaturesBruteForce(int[] temperatures) {
        int n = temperatures.Length;
        int[] result = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    result[i] = j - i;
                    break;
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n²) - For each element, scan the remaining elements
  • Space Complexity: O(1) excluding the output array

Key Insights

  1. Monotonic Stack: Use stack to maintain decreasing order of temperatures
  2. Index Tracking: Store indices in stack to calculate day differences
  3. Efficient Processing: Each element is processed at most twice (push and pop)
  4. Next Greater Element: This is a variant of the next greater element problem
  5. Stack Property: Stack maintains temperatures in decreasing order

Edge Cases

  1. Single Day: [73] → [0]
  2. All Same: [70,70,70] → [0,0,0]
  3. Increasing: [30,40,50,60] → [1,1,1,0]
  4. Decreasing: [60,50,40,30] → [0,0,0,0]
  5. Mixed: [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]

Test Cases

def test_daily_temperatures():
    # Basic case
    assert dailyTemperatures([73,74,75,71,69,72,76,73]) == [1,1,4,2,1,1,0,0]
    
    # Single day
    assert dailyTemperatures([73]) == [0]
    
    # All same
    assert dailyTemperatures([70,70,70]) == [0,0,0]
    
    # Increasing
    assert dailyTemperatures([30,40,50,60]) == [1,1,1,0]
    
    # Decreasing
    assert dailyTemperatures([60,50,40,30]) == [0,0,0,0]
    
    print("All tests passed!")

test_daily_temperatures()

Follow-up Questions

  1. Next Greater Element: How would you find the next greater element?
  2. Previous Greater Element: How would you find the previous greater element?
  3. Circular Array: What if the array is circular?
  4. Multiple Queries: How would you handle multiple queries efficiently?
  5. Range Queries: What if you need to answer range queries?

Common Mistakes

  1. Wrong Stack Order: Not maintaining decreasing order in stack
  2. Index Confusion: Mixing up temperature values and indices
  3. Edge Cases: Not handling cases with no warmer days
  4. Stack Operations: Incorrect push/pop operations

Interview Tips

  1. Clarify Requirements: Ask about edge cases and constraints
  2. Discuss Approaches: Mention both brute force and stack approaches
  3. Explain Algorithm: Walk through the monotonic stack process
  4. Handle Edge Cases: Discuss scenarios with no warmer days
  5. Optimize Space: Consider space-time tradeoffs

Variations

  1. Next Greater Element: Find the next greater element instead of days
  2. Previous Greater Element: Find the previous greater element
  3. Circular Array: Handle circular arrays
  4. Multiple Queries: Handle multiple queries efficiently
  5. Range Queries: Answer range queries about temperatures