Last Updated: 13 Dec, 2020
Maximum In All Sub-Arrays Of Size K
Easy
Asked in companies
Given an array/list ‘ARR’ of integers and an integer ‘K’. You are supposed to return the maximum for every subarray of the given array of length ‘K’.
Note :
An array ‘B’ is a subarray of an array ‘A’ if ‘B’ that can be obtained by deletion of, several elements(possibly none) from the start of ‘A’ and several elements(possibly none) from the end of ‘A’.
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 integers separated by single space ‘N’ and ‘K’ denoting the number of elements in the array/list and the length of the subarray.
The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output Format :
For each test case, print a single line that contains ‘N’ - ‘K’ + 1 space-separated integers denoting the maximum for each subarray in the following sequence:
[0, K-1], [1, K], . . . , [N-K, N-1] where [i, j] denotes the maximum element in the subarray starting from the ith index and ending with jth index.
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 ith elements of the given array/list.
Time Limit: 1 sec
Approaches
The basic idea of this approach is to iterate through all the possible subarrays of length K and then find the maximum of each subarray.
Let’s assume a window of size K denoting a subarray. Now we can slide this window to get every possible subarray of the given array. Next, our task would be to find the maximum number in the window.
Consider the steps as follows :
- Create a loop and start iterating using a variable low which denotes the lower end of the window. The range of the low value will be [0, N - K].
- In a nested loop, find the maximum value inside the window for each iteration. This way we will be able to get the maximum for all possible subarrays of length K.
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 and dictionary in Python) to perform this task.
Consider the following figure to see what happens when we move the window described in Approach1.
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 :
- Initialize an ordered_map<int, int> window, which is used to store the frequency of elements. Iterate through the elements of the subarray [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 :
- Insert the element at index high in the window i.e . window[ARR[high]] = window[ARR[high]] + 1
- Store the maximum of the current window which would be the first element, i.e. return window->begin().first.
- Remove the element at index high - K + 1 from the window.
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 element.
Now consider the explanation in the following image for a better understanding of the working of the deque.
Consider the steps as follows :
- 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, remove 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 subarray 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 subarray.
- 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 (or subarray) which is at the front of the deque. Store the maximum element of the current subarray.
Similar problems