739. Daily temperatures Leetcode Solution
Daily temperatures Leetcode Problem :
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.
Daily Temperature Leetcode Solution :
Constraints :
- 1 <= temperatures.length <= 10^5
- 30 <= temperatures[i] <= 100
Example 1:
- Input: temperatures = [30,40,50,60]
- Output: [1,1,1,0]
Example 2:
- Input: temperatures = [30,60,90]
- Output: [1,1,0]
Intuition :
The problem involves finding the number of days one has to wait until a warmer temperature is reached. A stack-based approach can efficiently track the temperatures and their indices while updating the answer.
- Initialize an empty stack stk to store temperatures and their corresponding indices.
- Initialize a vector ans of the same length as the input temperatures to store the number of days to wait for each temperature. Initialize all values in ans to 0.
- Iterate through the temperatures vector. For each temperature t at index i:
- While the stack is not empty and the current temperature t is greater than the temperature on top of the stack, pop temperatures from the stack and update the corresponding ans values with the number of days to wait.
-
Push the current temperature t and its index i onto the stack.
- After processing all temperatures, the ans vector contains the number of days to wait for each temperature.
- Return the ans vector as the result.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
vector< int> dailyTemperatures(vector< int>& temperatures) {
vector< int> ans(temperatures.size(),0);
stack< pair< int,int>> stk;
for( int i = 0 ; i < temperatures.size() ; i++){
int t = temperatures[i];
while(stk.empty()==false && t>stk.top().first){
pair< int,int> temp = stk.top();
stk.pop();
ans[temp.second]=(i-temp.second);
}
stk.push({t,i});
}
return ans;
}
};
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] answer = new int[temperatures.length];
Stack indices = new Stack<>();
for (int i = 0; i < temperatures.length; i++){
if (i+1 >= temperatures.length){
answer[i] = 0;
while((!indices.isEmpty())){
answer[indices.pop()] = 0;
}
}
else{
if (temperatures[i] < temperatures[i+1]){
while((!indices.isEmpty()) && (temperatures[indices.peek()] < temperatures[i+1])){
answer[indices.peek()] = i+1 - indices.pop();
}
answer[i] = 1;
}
else{
indices.push(i);
}
}
}
return answer;
}
}
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
ans=[0]*len(temperatures)
stack=[]
for i , t in enumerate(temperatures):
while stack and t > stack[-1][0]:
tempt ,tempi= stack.pop()
ans[tempi] = i - tempi
stack.append([t,i])
return ans
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment