Maximum of all subarrays of size k

Problem Statement:

Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer 'N' denoting the size of array and the size of subarray 'k'.
The second line contains 'N' space-separated integers A1, A2, ..., AN denoting the elements of the array.

Output:
Print the maximum for every subarray of size k.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ k ≤ N
0 ≤A[i]<1000

Example:

Input:
2
9 3
1 2 3 1 4 5 2 3 6
10 4
8 5 10 7 9 4 15 12 90 13

Output:
3 3 4 5 5 5 6
10 10 10 15 15 90 90

Video Tutorial 

Code:

import java.util.*; import java.lang.*; import java.io.*; class Subarray { public static void main (String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for(int u=0;u<t;u++) { int n=sc.nextInt(); int k=sc.nextInt(); int arr[]=new int[n]; //dequeue ArrayList <Integer> al=new ArrayList<Integer>(); //ArrayList to store the result ArrayList <Integer> res=new ArrayList<Integer>(); for(int i=0;i<n;i++) { arr[i]=sc.nextInt(); } //adding first window into dequeue //add indexes to the dequeue for(int i=0;i<k;i++) { if(al.size()==0) { al.add(i); } else { while(al.size()!=0 && arr[i]>arr[al.get(al.size()-1)]) { al.remove(al.size()-1); } al.add(i); } } //deque will be sorted in descending order res.add(arr[al.get(0)]); //for rest of the window process element one by one for(int i=k;i<n;i++) { while(al.size()!=0 && al.get(0)<=i-k) { al.remove(0); } while(al.size()!=0 && arr[i]>arr[al.get(al.size()-1)]) { al.remove(al.size()-1); } al.add(i); res.add(arr[al.get(0)]); } for(int i=0;i<res.size();i++) { System.out.print(res.get(i)+" "); } System.out.println(" "); } } }