LeetCode Problem: 739. Daily temperatures.

Problem Statement:

Given an array which consists of daily temperatures, find out what is the warmth upcoming day in the list. If there is no such day exist return 0. Suppose the array of temperature is:

60, 70, 80, 77, 73, 79, 81, 75

Answer should be 1, 1, 4, 2, 1, 1, 0, 0.

Explanation:

Immediate warmth day after 60 is 70 which is next day, so 1. Same for 70 as well. But for 80 next warmth day is 81 which is after 4 days, for 77 it is 79 which is the second day, for 73 it is 79 which is next day. But there is no day in the list where temperature is greater than 81 so insert 0 same for 75 as well.

Solution with Explanation:

• The idea is to use stack data structure to keep track of which we didn't find the warmth temperature in next day.
• First day temperature is pushed into the stack
• On second day we check the top value of stack is less than the current day temperature.
• If yes, then we found the immediate warmth day for the day which is on top of the stack.
• We pop that and check whether next top value is also less than current day temperature.
• If yes, follow above steps else push current day temperature into the stack and go to next day.

Code in C++

class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
    stack<pair<int, int>> stk;
    vector<int> ans(T.size(), 0);
    for(int iter = 0; iter < T.size(); ++iter){
        while(!stk.empty() && (T[iter] > stk.top().first)){
                ans[stk.top().second] = iter - stk.top().second;
                stk.pop();
        }
        stk.push({T[iter], iter});
    }
    return ans;
    }
};