Maximum in Subarrays of length K — Asked in Amazon Interview

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

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.

Sample Input:

6 3
10 5 2 7 8 7

Sample Output:

10 7 8 8

Approach :

Deque Approach

1. Create a double-ended queue. Note that the deque will store the indices of the elements, not the elements themselves
2. 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.
3. 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.
4. 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.

Time Complexity — O(N)
Space Complexity — O(K)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.