Complexity Analysis: The time complexity of this approach is O(N^2). In the worst-case scenario (e.g., a sorted decreasing array like [99, 98, 97, ...]), for every element i, we scan all remaining N-1-i elements. With constraints allowing N up to 100,000, an O(N^2) solution performs approximately 10 billion operations, which results in a Time Limit Exceeded (TLE) error.

Core Insight for Daily Temperatures

The inefficiency of the brute force approach stems from redundant comparisons. We repeatedly scan the same future elements for different past days.

The core insight of the Monotonic Stack pattern here is to process the array linearly while maintaining a "pending" list of days. Instead of looking forward from the current day, we look backward at previous days that haven't found a warmer day yet.

We maintain a stack of indices. The invariant we enforce is that the temperatures corresponding to the indices in the stack are in strictly decreasing order.

Why decreasing?

1. As we iterate through the array, if the current temperature is colder than the temperature at the top of the stack, we cannot resolve the answer for the stack top yet. We push the current index onto the stack.
2. If the current temperature is warmer than the temperature at the top of the stack, we have found the "next greater element" for the day at the stack top. We pop the index, calculate the distance, and repeat this check for the new stack top.

Visual Description: Imagine iterating through the array. The stack acts as a container for indices of days with "unresolved" temperatures.

• When we encounter a temperature of 75, and the stack top represents a day with 72, we know 75 is the warmer day 72 was waiting for.
• We "resolve" 72 by popping it and calculating the difference in indices.
• We continue popping until the stack is empty or the top represents a temperature greater than or equal to 75.
• Finally, we push the index of 75 onto the stack, as it is now waiting for a future warmer day.

Execution Flow

Let's trace temperatures = [73, 74, 75, 71, 69, 72, 76, 73].

1. i = 0 (73): Stack is empty. Push 0. Stack: [0].
2. i = 1 (74): 74 > temperatures[0] (73).
   • Pop 0. answer[0] = 1 - 0 = 1.
   • Stack empty. Push 1. Stack: [1].
3. i = 2 (75): 75 > temperatures[1] (74).
   • Pop 1. answer[1] = 2 - 1 = 1.
   • Stack empty. Push 2. Stack: [2].
4. i = 3 (71): 71 < 75. Push 3. Stack: [2, 3]. (Note: temps are decreasing 75 -> 71).
5. i = 4 (69): 69 < 71. Push 4. Stack: [2, 3, 4]. (Temps: 75 -> 71 -> 69).
6. i = 5 (72): 72 > temperatures[4] (69).
   • Pop 4. answer[4] = 5 - 4 = 1. Stack: [2, 3].
   • Check Top: 72 > temperatures[3] (71).
   • Pop 3. answer[3] = 5 - 3 = 2. Stack: [2].
   • Check Top: 72 < temperatures[2] (75). Stop popping.
   • Push 5. Stack: [2, 5].
7. i = 6 (76): 76 > temperatures[5] (72).
   • Pop 5. answer[5] = 6 - 5 = 1.
   • 76 > temperatures[2] (75).
   • Pop 2. answer[2] = 6 - 2 = 4.
   • Push 6. Stack: [6].
8. i = 7 (73): 73 < 76. Push 7. Stack: [6, 7].
9. End: Remaining indices 6 and 7 have answer 0.

Proof of Correctness

The algorithm is correct because it strictly adheres to the definition of the problem. We only pop an index prev_index when we find a current index i such that temperatures[i] > temperatures[prev_index]. Since we iterate from left to right, the first time this condition is met for prev_index, i is guaranteed to be the nearest future day with a warmer temperature. The Stack invariant (strictly decreasing temperatures) ensures that any index remaining in the stack has not yet encountered a warmer temperature.

Reference Implementation

C++ Solution for LeetCode 739

cpp
#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
        int n = temperatures.size();
        std::vector<int> answer(n, 0);
        std::stack<int> st; // Stores indices

        for (int i = 0; i < n; ++i) {
            // While stack is not empty and current temp is warmer than
            // the temp at the index stored at the top of the stack
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int prevIndex = st.top();
                st.pop();
                answer[prevIndex] = i - prevIndex;
            }
            st.push(i);
        }

        return answer;
    }
};

Java Solution for LeetCode 739

java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        // Using ArrayDeque is generally faster than Stack in Java
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // Check if current temp is warmer than the temp at the top index
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }

        return answer;
    }
}

Python Solution for LeetCode 739

python
from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = [] # Stores indices

        for i, current_temp in enumerate(temperatures):
            # While stack is not empty and current temp is warmer
            while stack and current_temp > temperatures[stack[-1]]:
                prev_index = stack.pop()
                answer[prev_index] = i - prev_index
            
            stack.append(i)
            
        return answer

• Mistake: Storing temperature values in the stack instead of indices.
• Why: If you store values (e.g., 73), you lose the information about where that temperature occurred.
• Consequence: You cannot calculate current_index - prev_index without the stored index.