Last Updated: 6 Jan, 2021
Maximum of All Subarrays of Size K
Easy
Asked in companies
You are given an array “A” of N integers. Your task is to find the maximum element in all K sized contiguous subarrays from left to right.
For Example:
If A = [3, 2, 3], and K = 2.
Then max of [3, 2] = 3 and max of [2, 3] = 3
So, the answer will be [3, 3]
If A = [3, 2, 3, 5, 1, 7] and K = 3.
Then max of [3, 2, 3] = 3
Then max of [2, 3, 5] = 5
Then max of [3, 5, 1] = 5
Then max of [5, 1, 7] = 7
So the answer will be [3, 5, 5, 7]
Follow Up :
Can you solve the problem in O(N) time complexity and O(K) space complexity?
Input format :
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test contains two space-separated integers N and K.
The second line of each test contains N space-separated integers, denoting the elements of array A.
Output format :
For each test case, print a single line containing N - K + 1 space-separated integers denoting values of the maximum element in K size subarrays.
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 <= A[i] <= 10^9
Time Limit: 1sec
Approaches
Steps:
- Declare an empty array to store a maximum of all K sized subarrays, say the answer.
- Generate all subarrays of size K using two nested loops.
- Find max in each of K sized subarrays and add it to the answer.
- Finally, Return the answer.
The idea is here to maintain a window of size K using a multiset containing exactly K elements for each window. Multiset allows us to perform both insertions of elements and getting the maximum element in a subarray in O(logK) time where K is the size of a multiset.
If the size of the multiset becomes greater than K, we remove the element which is K distance before our current index.
Steps :
- Declare an empty array to store a maximum of all sized subarrays, say the answer.
- Declare a multiset, say the window to maintain a window of maximums of size K.
- Run a loop and iterate through all elements of the array, and do:
- Insert current element to the window.
- If the window size becomes greater than K, remove the element that then is not part of the window, i.e. element having index as current index – K.
- If the size of the window becomes equal to K i.e. when the current index becomes at least K then add the maximum element of the window to answer.
- Finally, Return the answer.
The idea is to divide the array into windows of size K, and store the maximum element of each window from left to right and right to left respectively
So we will maintain two windows one will store maximums from left to right, say leftWindow and the other will store maximums from right to left, say rightWindow
Then we will calculate the answer for the window starting from index i as a maximum of leftWindow[i + k - 1] and rightWindow[i].
Refer to the below image for a better understanding.
Here we need to calculate the maximum in the subarray from X to Y and the size of this subarray is K.
We can get the maximum of this subarray by getting a maximum of the orange window and a maximum of a red window.
Maximum of orange window = rightWindow[X]
Maximum of red window = leftWindow[Y]
So the maximum of this subarray will be the maximum of rightWindow[X] and leftWindow[Y].
Steps :
- Declare an array to store a maximum of all K-sized subarrays, say the answer.
- Declare two empty arrays leftWindow and rightWindow to store maximums from left to right and right to left respectively.
- Run a loop and build leftWindow.
- Run a loop and build rightWindow.
- Run a loop till N - K, where N is the total number of elements in the array and K is the size of subarray given in the problem
- Let's denote the current index of the loop using i, then answer[i] = maximum of leftWindow[i + k - 1] and rightWindow[i].
- At last return answer.
The idea is here to maintain a window of size K using deque and store indices of maximum elements in the deque.
We will maintain a deque such that the front element is maximum, then the next element is second maximum, and so on.
We will insert elements one by one. If the indices of the maximum element of the window are out of bound i.e. not lies in the current window then we will remove it.
Then we will remove the rightmost indices of deque until the element at this index is smaller than the current element. We don’t need smaller indices of windows since they don’t contribute anything to our answer.
Steps :
- Declare an empty array to store a maximum of all K-sized subarrays, say the answer.
- Declare an empty deque to maintain a window of indices, say indexWindow.
- Run a loop and iterate through all elements of the array, and do:
- If the front element of the deque is out of bound from the current window then remove it.
- Remove the rightmost indices of deque until the element at this index is smaller than the current element.
- Push index of the current element at the back of the window.
- If the size of the window becomes equal to K i.e. when the current index becomes at least K then add the maximum element of the window to answer i.e. element having index equals to the front element of the deque.
- Finally, Return the answer.
Similar problems