Maximum of All Subarrays of Size k

Given an array of 'N' non-negative integers and an integer 'K', your task is to find the maximum elements for each subarray of size 'K'.

Input:

The first line contains an integer 'T', the number of test cases. The first line of each test case contains two integers 'N' and 'K'. The second line of each test case contains 'N' integers representing the array.

Output:

For each test case, print a line with 'X' integers, where 'X' is the number of subarrays of size 'K'. Each integer denotes the maximum element of the respective subarray.

Example:

Input:

2 5 3 1 3 2 4 5 6 4 8 5 10 7 9 4

Output:

3 4 5 10 10 10

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 10⁵

1 ≤ K ≤ N

1 ≤ arr[i] ≤ 10⁹

Time Limit: 1 sec

Note:

A subarray is a contiguous subset of an array and the array may contain duplicate elements. The array follows 0-based indexing and it’s guaranteed that at least one subarray of size 'K' exists.

Question

Maximum of All Subarrays of Size k

Given an array of 'N' non-negative integers and an integer 'K', your task is to find the maximum elements for each subarray of size 'K'.

Input:

The first line contains an integer 'T', the number of test cases.
The first line of each test case contains two integers 'N' and 'K'.
The second line of each test case contains 'N' integers representing the array.

Output:

For each test case, print a line with 'X' integers, where 'X' is the number of subarrays of size 'K'. Each integer denotes the maximum element of the respective subarray.

Example:

Input:

2
5 3
1 3 2 4 5
6 4
8 5 10 7 9 4

Output:

3 4 5
10 10 10

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 10⁵
1 ≤ K ≤ N
1 ≤ arr[i] ≤ 10⁹
Time Limit: 1 sec

Note:

A subarray is a contiguous subset of an array and the array may contain duplicate elements. The array follows 0-based indexing and it’s guaranteed that at least one subarray of size 'K' exists.

Accepted Answer

The task is to find the maximum elements for each subarray of size K in a given array.

Iterate through the array and maintain a deque of indices of the maximum elements in the current window of size K.
For each new element, remove indices from the deque that are outside the current window.
Add the index of the new element to the deque, and print the maximum element of the window if the first index in the deque is outside the window.

Maximum of All Subarrays of Size k

Input:

Output:

Example:

Input:

Output:

Constraints:

Note:

Top Decimal Point Analytics Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern