739. Daily Temperatures

📝 Problem Details

• Title: 739. Daily Temperatures
• Link: https://leetcode.com/problems/daily-temperatures/
• Difficulty: Medium
• Tags/Categories: Stack
• Neetcode Reference: Video Link

---

🔍 Problem Understanding

Given a list of daily temperatures, the task is to calculate how many days you have to wait until a warmer temperature. If there is no future day with a warmer temperature, the output for that day should be 0.

---

🎯 Key Insights

- using a stack is helpful to keep track of indicies of temperatures that haven't yet found a warmer day

---

🔑 Approach

• Iterate Through the List:

  • Use a stack to store pairs (index, temperature) where the temperature is waiting for a warmer day.

• Process Stack Elements:

  • If the current temperature is higher than the temperature on top of the stack, calculate the difference in days and store it in the result array.
  • Continue popping the stack while this condition holds.

• Push Current Day:

  • Push the current day and its temperature onto the stack.

• Final Result:

  • For any remaining indices in the stack, there are no warmer days, so their result remains 0.

---

⌛ Complexity Analysis

Time Complexity: O(n)
	- each temperature is pushed and popped from the stack at most once
	- we are also iterating n times through the temperatures array

Space Complexity: O(n)
	- in the worst case all temperatures might be stored in the stack 

---

💻 Implementation of Solution

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<pair<int,int>> stk;
        vector<int> result(n);
 
        for(int i=0; i<n; i++){
            int currDay = i;
            int currTemp = temperatures[i];
 
            while(!stk.empty() && stk.top().second < currTemp){
                int prevDay = stk.top().first;
                int prevTemp = stk.top().second;
                stk.pop();
                result[prevDay] = currDay - prevDay;
            }
 
            stk.push({currDay, currTemp});
        }
 
        return result;
    }
};