DAY 107 - Daily Temperatures

Hey Guys!, Welcome to DAY 107 of #100DaysOfCode challenge.
Let's get right into our question.

Question: Daily Temperatures

Given an array of integers temperatures represents 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]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Problem Breakdown:

• We have been given an array temperatures which contains temperatures on n different days.

• We need to find out for the i'th day , how many days do we need to wait to experience a temperature greater than it. If we can't find a temperature warmer than it, then we must return 0.

• So the question is pretty straightforward, let's see how we can solve this.

Intuition:

• We can go through every temperature using a for loop and then we can use another loop to find the temperature that is greater to our current temperature.
• We can use this approach but it is of the order (N²), so we can probably do better than this.
• Let's look at it this way, at once we need to maintain how much data, we definitely need the prevDay and prevTemp for comparison and we need the current day as we are traversing through.
• Surely we have a data structure we can use to remember our previousTemperatures. It should be stack here as we can use extra memory.
• We will keep temperatures in our stack, and if we encounter a greater value, we shall subtract the days and push them into our answer.
• But for sure, we will be faced with the challenge in which our stack would be holding decreasing temperatures,
• For that, suppose we do encounter a temp greater than current top of the stack but not all the members in the stack we need to pop our stack until we have found the element less than equal to the current top.

Approach:

To solve this problem efficiently, we can use a stack to keep track of the indices of the temperatures in the list. Here's the step-by-step approach:

1. We initialize an empty stack st to store pairs of (index, temperature).

2. We also initialize an empty vector answer of the same size as the input list to store the number of days to wait for each day.

3. We iterate through the input list of temperatures, where i represents the current day.

4. For each day, we check if the stack is not empty, and the temperature at the top of the stack is less than the current temperature. If this condition is met, it means we have found a warmer day for the day at the top of the stack.

5. We pop elements from the stack and calculate the number of days to wait for each of them. For each popped element (prevDay, prevTemp), we calculate i - prevDay, which represents the number of days to wait until a warmer temperature is encountered.

6. We update the corresponding position in the answer vector with the calculated number of days.

7. Finally, we push the current day and temperature onto the stack and continue to the next day.

8. After processing all the days, we return the answer vector, which contains the number of days to wait for each day.

Code:

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();

        // pair: [index, temp]
        stack<pair<int, int>> st;
        vector<int> answer(n);

        for (int i = 0; i < n; i++) {
            int currDay = i;
            int currTemp = temperatures[i];

            while (!st.empty() && st.top().second < currTemp) {
                int prevDay = st.top().first;
                int prevTemp = st.top().second;
                st.pop();

                answer[prevDay] = currDay - prevDay;
            }

            st.push({currDay, currTemp});
        }

        return answer;
    }
};

Time and Space Complexity

Let's analyze the time and space complexity of our solution:

• Time Complexity: We iterate through the input list once, performing constant-time operations for each day. Therefore, the time complexity is O(N), where N is the number of days.

• Space Complexity: We use a stack to store at most N elements in the worst case (when temperatures are strictly increasing). Additionally, we use the answer vector of size N. Thus, the space complexity is O(N).