Given an array/list ‘ARR’ of integers and an integer ‘K’. You are supposed to return the maximum for every subarray of the given array of length ‘K’.
Note :An array ‘B’ is a subarray of an array ‘A’ if ‘B’ that can be obtained by deletion of, several elements(possibly none) from the start of ‘A’ and several elements(possibly none) from the end of ‘A’.
The first line contains a single integer ‘T’ denoting the number of test cases. The 'T' test cases follow.
The first line of each test case contains two integers separated by single space ‘N’ and ‘K’ denoting the number of elements in the array/list and the length of the subarray.
The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output Format :
For each test case, print a single line that contains ‘N’ - ‘K’ + 1 space-separated integers denoting the maximum for each subarray in the following sequence:
[0, K-1], [1, K], . . . , [N-K, N-1] where [i, j] denotes the maximum element in the subarray starting from the ith index and ending with jth index.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= 'T' <= 50
1 <= 'N' <= 10^4
1 <= 'K' <= 'N'
0 <= 'ARR[i]' <= 10^5
Where 'ARR[i]' denotes the ith elements of the given array/list.
Time Limit: 1 sec
2
5 3
3 6 5 4 3
4 2
7 2 5 4
6 6 5
7 5 5
In the first test case, 3 subarrays of length 3 are possible:
[0, 2], elements in the subarray are: {3, 6, 5} and the maximum is 6
[1, 3], elements in the subarray are: {6, 5, 4} and the maximum is 6
[2, 4], elements in the subarray are: {5, 4, 3} and the maximum is 5
In the second test case, 3 subarrays of length 2 are possible:
[0, 1], maximum of {7, 2} is 7
[1, 2], maximum of {2, 5} is 5
[2, 3], maximum of {5, 4} is 5
2
5 5
1 2 3 4 5
5 1
3 5 6 2 9
5
3 5 6 2 9
In the first test case, 1 subarray of length 5 is possible. The maximum of {1, 2, 3, 4, 5} is 5.
In the second test case, 5 subarrays of length 1 are possible. The maximum of each subarray is {3, 5, 6, 2, 9}, the array/list itself.
Can you try to find the maximum for all possible subarrays of length K?
The basic idea of this approach is to iterate through all the possible subarrays of length K and then find the maximum of each subarray.
Let’s assume a window of size K denoting a subarray. Now we can slide this window to get every possible subarray of the given array. Next, our task would be to find the maximum number in the window.
Consider the steps as follows :
O(N^2), where N is the number of elements in the given array/list.
Since we are using a sliding window technique where the window is moving through the array for N - K + 1 times, and we are finding the maximum element in the window of size K every time, so the overall time complexity will be O(N * K) or we can cay O(N^2).
O(N), where N is the number of elements in the given array/list.
Since we are using an array/list to store the maximum element of each subarray of length ‘K’. And there can be N - K + 1 such subarrays. So the overall space complexity will be O(N).