Maximum In Sliding Windows Of Size K

PROBLEM STATEMENT

Given an array/list of integers of length ‘N’, there is a sliding window of size ‘K’ which moves from the beginning of the array, to the very end. You can only see the ‘K’ numbers in a particular window at a time. For each of the 'N'-'K'+1 different windows thus formed, you are supposed to return the maximum element in each of them, from the given array/list.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases. The 'T' test cases follow.

The first line of each test case contains two single space-separated integers ‘N’ and ‘K’ denoting the number of elements in the array/list and the size of the window size respectively.

The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.

Output format :

For each test case, print the output array/list which contains the sliding window maximum in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 10^4
1 <= K <= N
0 <= ARR[i] <= 10^5

Where, ARR[i] denotes the i-th element in the array/list.

Time Limit: 1 sec.

Approach 1

Our intuition here is to go through each sliding window and keep track of the maximum element in each sliding window. To implement the same we run two nested loops, where the outer loop which will mark the starting point of the subarray of length k, the inner loop will run from the starting INDEX to INDEX + K, K elements from starting index and store the maximum element among these K elements into the answer.

STEPS :

Use two nested loops.
The outer loop from starting INDEX = 0 to N - K th elements.
The inner loop will run for ‘K’ iterations for the window size of ‘K’.
Now create a variable to store the maximum of K elements that are traversed in the inner loop.
Find the maximum of K elements traversed by the inner loop.
Store the maximum element in every iteration of the outer loop which is nothing but the sliding window maximum of the current window.

Try Problem

Approach 2

The basic idea of this approach is to use an efficient data structure for querying the maximum element in the window.

We can use an ordered_map in C++ (TreeMap in java) to perform this task.

Consider the following figure to see what happens when we move the window.

We can observe that when we slide our window, which is currently denoting a subarray [0, 2], two things happen :

Element at index 0 is removed.
And the element at index 3 is added.

Now, we just want to get the maximum element in our updated window. The above task can easily be done using the ordered_map efficiently. Therefore we will use an ordered_map for storing the elements of the window. Since insertion, the deletion and query for the maximum element can be done in O(logN) time in the ordered_map. This approach would be more efficient than the previous one.

Consider the steps as follows :

Initialise an ordered_map<int, int> window, which is used to store the frequency of elements. Iterate through the elements of the window [0, K-2] and store the frequencies in the window.
Create a loop and start iterating using a variable “high” which denotes the higher end of the window, which will be initially at ‘K’-1.
At each iteration :
1. Insert the element at index “high” in the window i.e . window[ARR[high]] = window[ARR[high]] + 1
2. Store the maximum of the current window which would be the first element, i.e. return window->begin().first.
3. Remove the element at index “high” - K + 1 from the window.

Try Problem

Approach 3

The basic idea of this approach is to use a deque to store the elements of the window. We will maintain a deque that will store elements in non-increasing order such that the maximum element of the window is at the front of the deque. We will store the index of the elements of the given array/list.

STEPS:

Initialize a deque window that stores the index of the element in the given array/list. And insert the first K - 1 element in the deque. While inserting in the back of the deque, check if the last element is less than the current element, if it is so, removes the element from the back of the deque until all elements are greater than the current element. Then, insert the current element at the back of the deque.
Start traversing the array from the front using an index i which denotes the end of the current window such that K - 1 <= i <= N - 1.
- Remove the front element from the deque if its index lies outside the boundary of the current window because the deque is used to store the index of the current window.
- Now, remove the elements from the back of the deque until the last element is greater than or equal to the current element because we want to maintain a non-increasing deque.
- Insert the index of the current element at the end of the deque.
- Get the maximum element of the current window which is at the front of the deque. Store the maximum element of the current window.
Return the final answer.

Try Problem