New update is available. Click here to update.

Last Updated: 28 Jul, 2020

Difficulty: Easy

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

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

```
0 <= N <= 5 * (10 ^ 5)
1 <= K <= N
Time Limit: 1 sec
```

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

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

SIMILAR PROBLEMS

Missing Number

Posted: 30 Oct, 2022

Difficulty: Easy

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Popular Interview Problems: