Last Updated: 18 Feb, 2021
Sum of minimum and maximum elements of all subarrays of size “K”
Moderate
Asked in companies
You are given an array consisting of N integers, and an integer, K. Your task is to determine the total sum of the minimum element and the maximum element of all subarrays of size K.
Note :
The array may contain duplicate elements.
The array can also contain negative integers.
The size of the array is at least 2.
There exists at least one such 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, denoting the number of elements in the array and the size of the subarray to be considered.
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, an integer denoting the total sum of minimum and maximum element in all subarrays of size K.
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 run a loop(say, loop variable i) through all the possible starting indices of such subarray.
- Run a nested loop(say, loop variable j) through the elements starting from index i up to the next K elements.
- Initialize two variables to store the minimum and maximum values of this subarray.
- At each iteration of the inner loop check and update the minimum value and the maximum value of that subarray.
- Finally, after the inner loop ends, add the maximum value and the minimum value of this subarray to our final sum.
- The idea behind this brute force approach is to use the sliding window technique.
- We can maintain a multiset that contains all the elements in that window.
- Initially, the multiset contains all elements of the first window of size K.
- Now we loop through all the remaining windows, starting from the Kth index.
- If the current window starts at index i, then i is the first element of this window and i+K-1 will be the last index of this window as the size of the window is K.
- For every new window, we delete one occurrence of the first element of the previous window from our multiset as now it is not in the current window.
- And we insert the last element of the current window into the multiset.
- For every window, we know the minimum element is the element that is at the first position in the multiset, and similarly, the maximum element will be at the last position.
- For every window, we can add both these values to our final answer.
- The idea behind this approach is to maintain two separate Dequeues(say, minDequeue and maxDequeue) which store the indices of the elements. In maxDequeue, we will maintain decreasing order of elements while in minDequeue we will maintain increasing order of elements. The idea for this approach is that we will keep only those elements that are candidates for our answer.
- We keep at max K element (i.e. the size of our window) in both the Dequeues and the current index is placed at its respective sorted place in both the Dequeues.
- To find maximum and minimum elements in the first window of size K, we run a loop through the first K elements of the array.
- While the minDequeue is not empty and the current element is smaller than or equal to the element at the rear end index of minDequeue, pop the rear element of minDequeue. This makes sure that we are getting rid of all those elements which can never be the minimum element in any subarray of size K and the minimum element for this subarray will be at the front end index.
- While the maxDequeue is not empty and the current element is greater than or equal to the element at the rear end index of maxDequeue, pop the rear element of maxDequeue. This makes sure that we are getting rid of all those elements which can never be the maximum element in any subarray of size K and the maximum element for this subarray will be at the front end index.
- Add the current index to the rear of both the Dequeues.
- Now, the front end index of minDequeue corresponds to the minimum element of this window of size K while the front end element of maxDequeue corresponds to the maximum element and we can add the elements at these two positions to our final sum.
- We have to repeat this process for the rest of the windows as well.
- But before inserting the current index we have to remove all indices in both the Dequeues which are not in the current window of size K.
- Since our current window ends at (say, index i), we have to remove all indices from both the Dequeues which are less than the starting index of this window (in this case, it would be i - K).
- While the index at the front end of minDequeue is less than or equal to the starting index of this window, remove the front end index of minDequeue.
- While the index at the front end of maxDequeue is less than or equal to the starting index of this window, remove the front end index of maxDequeue.
- Now, we can follow the above process to insert the current element into both the Dequeues.
- For, every iteration, the front end index of minDequeue will correspond to the minimum element of that window while the front end index of maxDequeue will correspond to the maximum element of that window and we can add both these elements to our final answer.