**Problem Link:**↵
------------------↵
↵
[Contest](https://www.hackerrank.com/contests/codehive/)<br/>↵
[Question](https://www.hackerrank.com/contests/codehive/challenges/max-avatar-time)↵
↵
**Author**: [Raj Pateuser:rajpate77725,2023-02-04]<br/>↵
↵
**DIFFICULTY:**↵
------------------↵
MEDIUM↵
↵
**PREREQUISITES:**↵
------------------↵
ARRAY ,SLIDING WINDOW↵
↵
**PROBLEM:**↵
------------------↵
On the lush alien world of Pandora live the Na'vi beings who appear primitive but are highly evolved.Doctor Grace runs a project which allows humans to transform in Avatar. Jake a paralyzed former Marine becomes mobile again through one such Avatar. Jake has been given a mission to become friends with the Na'vi people by transforming into Avatar.↵
↵
The project runs for N days where on each day Jake can transform into Avatar for a specific amount of time. Through her experience, Doctor Grace can predict the transformation time of Jake for maximum K days. After each prediction, the next prediction occurs after F days.↵
↵
Find the maximum Avatar time in each prediction.↵
↵
**EXPLANATION:**↵
------------------↵
Observations:↵
- Checkup is happening after every F days.↵
- Out of f days trasformation can be predicted for max k days.↵
↵
Approach:↵
- We can use sliding window approach such that window slides after every F days and first k days of every F days can be choosen for a search of max element.↵
↵
- We used the deque to store the required index of max element after every iteration.↵
- Whenever the max element comes we pop_back the element less than that element from the deque such that only the maximum element left at the back of the deque.↵
- Corner case is there for the elements after the every possible window size.↵
- After that we have the array of max element in every k interval.↵
- Then we print the element in the interval of f elements.↵
↵
**TIME COMPLEXITY:**↵
------------------↵
**O(N)** per test case.↵
↵
**CODE:**↵
------------------↵
↵
<spoiler summary="Editorialist's Code(C++)">↵
```c++↵
//JAY SHREE RAM↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void slidingWindowMaximum(vector<int>nums, vector<int>&ans, int k){↵
int n=nums.size();↵
deque<int>dq;↵
for(int i=0;i<nums.size();i++){↵
if(!dq.empty() && dq.front()==i-k){↵
//sliding window ↵
dq.pop_front();↵
}↵
while(!dq.empty() && nums[dq.back()] < nums[i]){↵
//removing lesser element than current element↵
dq.pop_back();↵
}↵
dq.push_back(i);↵
if(i>=k-1){↵
ans.push_back(nums[dq.front()]);↵
}↵
}↵
↵
vector<int>rem(k-1);↵
int mx=0;↵
// corner case↵
for(int i=0;i<k-1;i++){↵
mx=max(mx,nums[n-i-1]);↵
rem[k-i-2]=mx;↵
}↵
for(int i=0;i<rem.size();i++){↵
ans.push_back(rem[i]);↵
}↵
↵
}↵
↵
int main(){↵
cin.tie(0), cout.tie(0),ios_base::sync_with_stdio(false);↵
int t;↵
cin>>t;↵
while(t--){↵
vector<int>nums;↵
int n,k,f;↵
cin>>n>>k>>f;↵
for(int i=0;i<n;i++){↵
int x;↵
cin>>x;↵
nums.push_back(x);↵
}↵
vector<int>ans;↵
slidingWindowMaximum(nums,ans,k);↵
↵
//here we are printing every f'th element.↵
for(int i=0;i<ans.size();i+=f){↵
cout<<ans[i]<<" ";↵
}cout<<endl;↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
------------------↵
↵
[Contest](https://www.hackerrank.com/contests/codehive/)<br/>↵
[Question](https://www.hackerrank.com/contests/codehive/challenges/max-avatar-time)↵
↵
**Author**: [
↵
**DIFFICULTY:**↵
------------------↵
MEDIUM↵
↵
**PREREQUISITES:**↵
------------------↵
ARRAY ,SLIDING WINDOW↵
↵
**PROBLEM:**↵
------------------↵
On the lush alien world of Pandora live the Na'vi beings who appear primitive but are highly evolved.Doctor Grace runs a project which allows humans to transform in Avatar. Jake a paralyzed former Marine becomes mobile again through one such Avatar. Jake has been given a mission to become friends with the Na'vi people by transforming into Avatar.↵
↵
The project runs for N days where on each day Jake can transform into Avatar for a specific amount of time. Through her experience, Doctor Grace can predict the transformation time of Jake for maximum K days. After each prediction, the next prediction occurs after F days.↵
↵
Find the maximum Avatar time in each prediction.↵
↵
**EXPLANATION:**↵
------------------↵
Observations:↵
- Checkup is happening after every F days.↵
- Out of f days trasformation can be predicted for max k days.↵
↵
Approach:↵
- We can use sliding window approach such that window slides after every F days and first k days of every F days can be choosen for a search of max element.↵
↵
- We used the deque to store the required index of max element after every iteration.↵
- Whenever the max element comes we pop_back the element less than that element from the deque such that only the maximum element left at the back of the deque.↵
- Corner case is there for the elements after the every possible window size.↵
- After that we have the array of max element in every k interval.↵
- Then we print the element in the interval of f elements.↵
↵
**TIME COMPLEXITY:**↵
------------------↵
**O(N)** per test case.↵
↵
**CODE:**↵
------------------↵
↵
<spoiler summary="Editorialist's Code(C++)">↵
```c++↵
//JAY SHREE RAM↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void slidingWindowMaximum(vector<int>nums, vector<int>&ans, int k){↵
int n=nums.size();↵
deque<int>dq;↵
for(int i=0;i<nums.size();i++){↵
if(!dq.empty() && dq.front()==i-k){↵
//sliding window ↵
dq.pop_front();↵
}↵
while(!dq.empty() && nums[dq.back()] < nums[i]){↵
//removing lesser element than current element↵
dq.pop_back();↵
}↵
dq.push_back(i);↵
if(i>=k-1){↵
ans.push_back(nums[dq.front()]);↵
}↵
}↵
↵
vector<int>rem(k-1);↵
int mx=0;↵
// corner case↵
for(int i=0;i<k-1;i++){↵
mx=max(mx,nums[n-i-1]);↵
rem[k-i-2]=mx;↵
}↵
for(int i=0;i<rem.size();i++){↵
ans.push_back(rem[i]);↵
}↵
↵
}↵
↵
int main(){↵
cin.tie(0), cout.tie(0),ios_base::sync_with_stdio(false);↵
int t;↵
cin>>t;↵
while(t--){↵
vector<int>nums;↵
int n,k,f;↵
cin>>n>>k>>f;↵
for(int i=0;i<n;i++){↵
int x;↵
cin>>x;↵
nums.push_back(x);↵
}↵
vector<int>ans;↵
slidingWindowMaximum(nums,ans,k);↵
↵
//here we are printing every f'th element.↵
for(int i=0;i<ans.size();i+=f){↵
cout<<ans[i]<<" ";↵
}cout<<endl;↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
