LeetCode Solution 739 - Daily Temperatures

Problem Statement

You are given an array temperatures where temperatures[i] represents the daily temperature on the i-th day. You need to return an array answer such that answer[i] is the number of days until a warmer temperature. If there is no future day with a warmer temperature, set answer[i] = 0.

Example

Input:

 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

Output:

 [1, 1, 4, 2, 1, 1, 0, 0]

---

Optimal Approach: Monotonic Stack

The best way to solve this problem efficiently is by using a Monotonic Decreasing Stack. This approach ensures that we only traverse the input array once while maintaining a stack of indices. The stack helps track the temperatures that haven't yet found a warmer day.

Algorithm Steps:

1. Initialize an empty stack.
2. Iterate through the temperature array:
   • While the stack is not empty and the current temperature is higher than the temperature at the index stored at the stack's top, update the answer for that index.
   • Push the current index onto the stack.
3. Any remaining indices in the stack have no warmer days, so their values remain 0.

---

LeetCode-Compatible C++ Solution

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

        for (int i = 0; i < n; i++) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int prevIndex = st.top();
                st.pop();
                answer[prevIndex] = i - prevIndex;
            }
            st.push(i);
        }
        return answer;
    }
};

---

Step-by-Step Explanation

1. We initialize a stack st to keep track of indices where we haven’t yet found a warmer day.
2. We iterate through temperatures:
   • If the current temperature is greater than the temperature at the index stored at the top of the stack, we update answer.
   • Otherwise, we push the current index to st.
3. After iteration, any remaining indices in the stack have no warmer temperatures, so they remain 0.

---

Dry Run with Sample Input

Given Input:

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

Execution:

Day	Temp	Stack (Indices)	Answer
0	73	[0]	[0, 0, 0, 0, 0, 0, 0, 0]
1	74	[1]	[1, 0, 0, 0, 0, 0, 0, 0]
2	75	[2]	[1, 1, 0, 0, 0, 0, 0, 0]
3	71	[2, 3]	[1, 1, 0, 0, 0, 0, 0, 0]
4	69	[2, 3, 4]	[1, 1, 0, 0, 0, 0, 0, 0]
5	72	[2, 5]	[1, 1, 0, 2, 1, 0, 0, 0]
6	76	[6]	[1, 1, 4, 2, 1, 1, 0, 0]
7	73	[6, 7]	[1, 1, 4, 2, 1, 1, 0, 0]

---

Alternative Approaches

1. Brute Force (Nested Loops)

Approach:

• Iterate through each temperature.
• Look ahead to find the next warmer day.

Complexity:

• Time Complexity: O(N²)
• Space Complexity: O(1)
• Why Not? Inefficient for large inputs.

2. Using HashMap

• Idea: Store temperature occurrences for quick lookups.
• Why Not? Difficult to track the sequence of days effectively.

3. Dynamic Programming (DP)

• Idea: Use a DP array to store the result for later days and compute results in reverse.
• Why Not? Still requires traversing the array multiple times.

---

Best Solution: Monotonic Stack

Approach	Time Complexity	Space Complexity	Efficiency
Brute Force	O(N²)	O(1)	❌ Slow
HashMap	O(N)	O(N)	❌ Not Effective
Dynamic Programming	O(N)	O(N)	❌ Extra Space
Monotonic Stack	O(N)	O(N)	✅ Best

The monotonic stack is the best approach since it efficiently tracks previous temperatures in a decreasing order and only processes each element once, leading to an optimal O(N) time complexity.

---

Conclusion

The Monotonic Stack approach provides an optimal O(N) solution for the Daily Temperatures problem. It efficiently determines the next warmer temperature without unnecessary computations.

Similar Problems for Practice:

1. Next Greater Element I
2. Largest Rectangle in Histogram
3. Stock Span Problem

This problem is a great example of leveraging stacks to solve range-based problems efficiently.