4)Maximum of all subarrays of size k -(Sliding Window | Fixed size)

Given an array arr[] of size N and an integer K. Find the maximum for each and every contiguous subarray of size K.

Example 1:

Input:
N = 9, K = 3
a[] = 1 2 3 1 4 5 2 3 6
Output: 
3 3 4 5 5 5 6 
Explanation: 
1st contiguous subarray = {1 2 3} Max = 3
2nd contiguous subarray = {2 3 1} Max = 3
3rd contiguous subarray = {3 1 4} Max = 4
4th contiguous subarray = {1 4 5} Max = 5
5th contiguous subarray = {4 5 2} Max = 5
6th contiguous subarray = {5 2 3} Max = 5
7th contiguous subarray = {2 3 6} Max = 6

Example 2:

Input:
N = 10, K = 4
a[] = 8 5 10 7 9 4 15 12 90 13
Output: 
10 10 10 15 15 90 90
Explanation: 
1st contiguous subarray = {8 5 10 7}, Max = 10
2nd contiguous subarray = {5 10 7 9}, Max = 10
3rd contiguous subarray = {10 7 9 4}, Max = 10
4th contiguous subarray = {7 9 4 15}, Max = 15
5th contiguous subarray = {9 4 15 12}, 
Max = 15
6th contiguous subarray = {4 15 12 90},
Max = 90
7th contiguous subarray = {15 12 90 13}, 
Max = 90

c++ implementation:

    vector <int> max_of_subarrays(int *a, int n, int k)
    {
           int i=0; int j=0;
           
        vector<int>v;
        deque<int>q;
        while(j<n)
        {

            while(!q.empty() && q.back()<a[j])
                    q.pop_back();
                   
                   q.push_back(a[j]);
        
            if(j-i+1==k)
            {
               v.push_back(q.front());
               
               if(q.front()==a[i])
               q.pop_front();
               
               i++;
            }
            
            j++;
        }                                           
        return v;  
    }

Time Complexity: O(n) 

space Complexity: O(n)