Problem of the day
You are given an array consisting of N non-negative integers, and an integer K denoting the length of a subarray, your task is to determine the maximum elements for each subarray of size K.
Note:A subarray is a contiguous subset of an array.
The array may contain duplicate elements.
The given array follows 0-based indexing.
It is guaranteed that there exists at least one subarray of size K.
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and K, as described in the problem statement.
The second line of each test case contains N space-separated integers, representing the elements of the array.
Output Format:
For each test case print in a new line, X space-separated integers, where X is the number of possible subarrays of size K, and the ith integer denote the maximum element of the ith possible subarray of size K starting from the left.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= N <= 10^5
1 <= K <= N
1 <= arr[i] <= 10^9
Time Limit: 1sec
1
4 2
10 7 8 11
10 8 11
The first subarray of length 2 is [10,7] and the maximum of it is 10, then the next subarray of length 2 is [7,8] and the maximum of it is 8, and the last subarray of size 2 is [8,11] and the maximum of it is 11, So the output is [10,8,11].
1
4 3
11 3 9 6
11 9
Consider each window of size K one by one.
O(N * K), where N is the number of elements in the array and K is the length of the subarray.
The time complexity is O(N * K) because the outer loop will run for the order of O(N) and the inner loop will run for the order of O(K), So the total complexity is O(N * K).
O(X), where X is the number of possible subarrays of size K.
We are storing the maximum of all the subarrays of size K, so the space complexity is O(X).