1.

Write a function to find the maximum for each and every contiguous subarray of size k.

Answer»


  • Input: N = 9, K = 3 arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}


  • Output: {3, 3, 4, 5, 5, 5, 6}


  • Explanation: In the first subarray of size 3: {1,2,3}, the value 3 is maximum, similarly for all such subarrays for size 3.

//function to find maximum in each subarray using sliding window approach
vector<int> max_of_subarrays(vector<int> arr, int n, int k){
int i=0,j=0;
deque<int> dq;
dq.push_front(i++);
while(i<k)
{
while(!dq.empty()&&arr[dq.back()]<=arr[i])
dq.pop_back();
dq.push_back(i++);
}
vector<int> ans;
while(i<n)
{
ans.push_back(arr[dq.front()]);
while(!dq.empty()&&j>=dq.front())
{
dq.pop_front();

}
j++;
while(!dq.empty()&&arr[dq.back()]<=arr[i])
dq.pop_back();
dq.push_back(i++);
}
ans.push_back(arr[dq.front()]);
return ans;

}


  • Time Complexity: O(n)


  • Space Complexity: O(k)


Discussion

No Comment Found

Related InterviewSolutions