LeetCode 739 – Daily Temperatures – Detailed Solution

Problem Understanding

Given an array of daily temperatures, we need to determine for each day how many days we must wait until a warmer temperature occurs. If no warmer temperature exists in the future, we should return 0 for that day.

Key Insights

1. Monotonic Stack: This problem is a classic example where a monotonic stack (specifically decreasing order) can be effectively used.

2. Stack Behavior: We maintain a stack of indices where the corresponding temperatures are in decreasing order. When we encounter a temperature higher than the temperature at the top of the stack, we know we’ve found a warmer day for that index.

3. Efficiency: The stack approach allows us to process each element at most twice (once when pushing, once when popping), resulting in O(n) time complexity.

Approach

1. Initialize an answer vector with all zeros (default case where no warmer day exists).

2. Use a stack to keep track of indices where we haven’t found a warmer day yet.

3. Iterate through each temperature:

   • While the current temperature is higher than the temperature at the top of the stack:

     • Pop the index from the stack.

     • Calculate the days difference (current index – popped index).

     • Store this difference in the answer vector at the popped index.

   • Push the current index onto the stack.

4. Return the answer vector.

Solution Code

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

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

        return answer;
    }
};

Explanation

1. Initialization: We start with an answer vector filled with zeros, which handles the case where no warmer day exists.

2. Stack Processing: As we iterate through each temperature:

   • We compare the current temperature with temperatures at indices stored in the stack.

   • For each index where we find a warmer temperature, we calculate the days waited and store it in the answer vector.

   • We maintain the stack in decreasing order of temperatures, ensuring we always have the most recent candidates for future warmer days.

3. Result: The answer vector is built progressively as we process each temperature, resulting in the correct number of days to wait for each day.

Example Walkthrough (temperatures = [73, 74, 75, 71, 69, 72, 76, 73])

1. i = 0 (73):

   • Stack is empty, push index 0.

   • Stack: [0]

2. i = 1 (74):

   • 74 > 73 (temperatures[0]), so pop 0.

   • answer[0] = 1 – 0 = 1.

   • Push index 1.

   • Stack: [1]

3. i = 2 (75):

   • 75 > 74 (temperatures[1]), so pop 1.

   • answer[1] = 2 – 1 = 1.

   • Push index 2.

   • Stack: [2]

4. i = 3 (71):

   • 71 <= 75, push index 3.

   • Stack: [2, 3]

5. i = 4 (69):

   • 69 <= 71, push index 4.

   • Stack: [2, 3, 4]

6. i = 5 (72):

   • 72 > 69 (temperatures[4]), pop 4.

     • answer[4] = 5 – 4 = 1.

   • 72 > 71 (temperatures[3]), pop 3.

     • answer[3] = 5 – 3 = 2.

   • 72 <= 75, push index 5.

   • Stack: [2, 5]

7. i = 6 (76):

   • 76 > 72 (temperatures[5]), pop 5.

     • answer[5] = 6 – 5 = 1.

   • 76 > 75 (temperatures[2]), pop 2.

     • answer[2] = 6 – 2 = 4.

   • Stack is empty, push index 6.

   • Stack: [6]

8. i = 7 (73):

   • 73 <= 76, push index 7.

   • Stack: [6, 7]

9. Final Answer:

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

Time and Space Complexity

• Time Complexity: O(n) – Each index is pushed and popped from the stack at most once.

• Space Complexity: O(n) – In the worst case, the stack could store all indices (for strictly decreasing temperatures).