Maximum in Subarrays of length K

PROBLEM STATEMENT

Given an array of integers of size N and a number K, print the maximum value of each subarray of length K in the array

Input Format:

The first line contains two single space separated integers, N and K.

The second line contains N single space separated integers denoting the elements of the array.

Output format:

A single line consisting of N - K + 1 single space separated integers denoting the maximum values of the K-sized subarrays where the subarrays are taken in a left to right fashion starting from the 0th index.

Constraints:

0 <= N <= 5 * (10 ^ 5)
1 <= K <= N

Time Limit: 1 sec

Approach 1

Create a nested loop. The outer loop will go from i = 0 to i = ‘N’ - ‘K’. This will cover the starting indices of all K-subarrays
The inner loop will go from j = i to j = i + K - 1. This will cover all the elements of the K-subarray starting from index i
Keep track of the maximum element in the inner loop and print it.

Try Problem

Approach 2

Create a double-ended queue. Note that the deque will store the indices of the elements, not the elements themselves
Insert the first ‘K’ elements (the first subarray) in the deque. While inserting the current element, check if the element at the back of the queue is smaller than the current element. If yes, then remove all those elements and then insert the current element in the back of the deque.
After you’ve done this, the front of the queue will have the index of the maximum element present in the first subarray of size ‘K’. Print the element present at front element (index of array element) of the deque.
Then, we’ll follow the same idea for the next elements as well but there will be one extra step which is to remove all elements from the front of the deque that is out of the range of the subarray into consideration.

Try Problem