Last Updated: 18 Feb, 2021
Maximum Of All Subarrays Of Size k.
Moderate
Asked in companies
You are given an array consisting of N non-negative integers, and an integer K denoting the length of a subarray, your task is to determine the maximum elements for each subarray of size K.
Note:
A subarray is a contiguous subset of an array.
The array may contain duplicate elements.
The given array follows 0-based indexing.
It is guaranteed that there exists at least one subarray of size K.
Input Format:
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and K, as described in the problem statement.
The second line of each test case contains N space-separated integers, representing the elements of the array.
Output Format:
For each test case print in a new line, X space-separated integers, where X is the number of possible subarrays of size K, and the ith integer denote the maximum element of the ith possible subarray of size K starting from the left.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
1 <= K <= N
1 <= arr[i] <= 10^9
Time Limit: 1sec
Approaches
- The Idea behind this brute force approach is to consider each subarray of size K by fixing a point i in the array and then consider all the points after it till we have considered K elements from the starting point i and finding the maximum element in it and then storing it.
- Now, run a loop(say, loop variable i) till (N-K) elements of the array:
- Run a nested loop(say, loop variable j) through the elements starting from index i up to the next k elements.
- At each iteration of the inner loop keep a track of the maximum element in that subarray and finally after the nested loop ends store the answer for this subarray and continue the process for next i.
- In the previous approach for finding the maximum element in the subarray we were iterating in the subarray of length K one by one, but we can optimize this step simply by using some data structure.
- In this approach, we will be using a set that will be storing the current element and its index (i.e. pair<int, int> where first is element and second is the index).
- Now at each point, our set will contain K elements and the last element will be the maximum element as the set contains elements in ascending order.
- So firstly, we will keep the first K element and its index in the set and iterate from the (K+1)th element to the last and simply remove the last element of the current window and insert the next element and its index in the set and at each iteration, the biggest element of the set is our answer for this window. I.e. remove {arr[i-K],i-K} from the set and insert {arr[i],i} in the set and the answer for this window will be (*st.rbegin()).first .
- In this approach, we will be using deque as we can further optimize the solution by deque.
- The idea for this approach is that we will keep only those elements that are candidates for our answer. The deque will always keep the index of the element in the sorted order from first to last i.e., the biggest element at the front and the smallest element at the last.
- We keep at max K element (i.e. the size of our window) in our deque and the current element is placed at its sorted place by popping all the smaller elements from the last so that the front element will always be the answer for this window.
- Since we also have to remove those elements from the deque which are now out of the current window, so we will compare the front element of the deque with the starting position of the current window and if the front element of the deque is smaller than the starting position of the window then we pop the front element. We do this till no element which is out of the current window is there.
- So we iterate the first K elements and keep the index of the maximum element of the first K elements from the array in our deque. Then iterate through the array from (K+1)th element till the last element and pop elements from the deque by comparing the last element of the deque to the current element (i.e. we pop the elements from the deque from the back till they are smaller than the current element (if(q.back()<nums[i])) then we pop the last element ) and finally placing the current element in its sorted position. We also pop the elements that are out of the current window from the front so at most K elements are only present in the deque.
- Example - let the given array is [1,3,6,2,7] and K = 3
- So initially our deque will have [2], as the maximum element in the first subarray of length K is 6 and its index is 2 and 6 will be our answer for the subarray [1,3,6].
- Now we iterate from index 3 to last. So our current window will be [3,6,2] and our current element will be 2 and q = [2].
- Firstly we check from the first if any element which is out of the window should not be present in the deque, so we check if the deque is containing elements smaller than 1 or not as our current window is from index [1,3].
- After that, we will compare our current element with the element whose index is denoted by the last element of the deque and if the element of the deque is smaller then we pop it. So our current element is 2 and the last element of deque is the element at the 2nd index i.e. 6, so we will not pop the element.
- And finally, we will push the index of the current element at the last. Therefore our deque will be, q = [2,3], so our answer for the subarray [3,6,2] will be 6 as it is the first element of the deque. After that our current window will become [6,2,7] and our current element will become 7.
- Finally again we check if any element is present in our deque which out of our current window i.e. [2,4] and after this checking we again check if our current element is bigger than the element represented by the last element of the deque. So firstly a comparison will be made between the current element = 7 and the last element of the deque = 2 so the last element of the deque will be popped. Now our deque q = [2].
- After that again a comparison will be made between the last element of the deque = 6 and the current element = 7, and again the last element of the deque will be popped. So now our deque will be empty ,q = []. So we will stop when our deque will become empty and finally push the current element in the deque, so our deque will be q = [4] and this element will be the answer of our current window i.e. 7.
- Therefore our answer will be [6,6,7].