Maximum Of All Subarrays Of Size k.

Moderate

0/80

Average time to solve is 20m

Contributed by

26 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

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.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
1 <= K <= N
1 <= arr[i] <= 10^9

Time Limit: 1sec

Sample Input 1:

1
4 2
10 7 8 11

Sample Output 1:

10 8 11

Explanation For Sample Input 1:

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].

Sample Input 2:

1
4 3 
11 3 9 6

Sample Output 2:

11 9

Console