Problem Title: K Sized Subarray Maximum

Problem Statement:

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
arr[] = 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
arr[] = 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
        

Your Task:

You don't need to read input or print anything. Your task is to complete the function max_of_subarrays() which takes the array arr[], its size N and an integer K as input parameters and returns a list of integers denoting the maximum of every contiguous subarray of size K.

• Expected Time Complexity: O(N)
• Expected Auxiliary Space: O(N)

Constraints:

• 1 ≤ N ≤ 10^6
• 1 ≤ K ≤ N
• 0 ≤ arr[i] ≤ 10^9

Java Code

class Solution
{
    //Function to find maximum of each subarray of size k.
    static ArrayList <Integer> max_of_subarrays(int arr[], int n, int k)
    {
        // Your code here
        ArrayList<Integer> list = new ArrayList<>();
        
        Deque<Integer> dq = new ArrayDeque<>();
        
        for(int i=0; i<n ; i++){
            
            //remove any out of bounds
            if(!dq.isEmpty() && dq.peek() == i-k){
                dq.poll();
            }
            
            //remove samller element befor adding
            
            while(!dq.isEmpty() && arr[dq.peekLast()] <= arr[i]){
                dq.pollLast();
            }
            
            //add i
            dq.offer(i);
            
            if(i >= k-1){
                list.add(arr[dq.peek()]);
            }
        }
        
        return list;
    }
}        

Explanation:

1. Create a list to store the maximum of each subarray.
2. Create a deque to store the index of the elements.
3. Iterate through the array.
4. Remove any out of bounds elements from the deque.
5. Remove any smaller elements from the deque.
6. Add the current index to the deque.
7. If the current index is greater than or equal to k-1, add the maximum element to the list.
8. Return the list.
9. The time complexity is O(N) and the space complexity is O(N).
10. The code is tested and verified against the provided test cases.