Sum of minimum and maximum of all subarrays of size k
Problem
For every contiguous window of size k, add its minimum and its maximum. Return the total over all windows.
Example 1
Input: arr = [2, 5, -1, 7, -3, -1, -2], k = 4 Output: 18
Windows give (−1+7) + (−3+7) + (−3+7) + (−3+7) = 18.
Also asked as: Sum of minimum and maximum elements of all subarrays of size “k”
Test cases
Case 1
Input: [2,5,-1,7,-3,-1,-2], 4 Expected: 18
Case 2
Input: [1,2,3], 1 Expected: 12
Case 3
Input: [1,2,3], 3 Expected: 4
Case 4
Input: [5,5], 2 Expected: 10
View solutionHide solution1 approach
1. Two monotonic deques (max and min)
Time O(n)Space O(k)
A decreasing deque gives the window max at its front; an increasing deque gives the window min. Slide and add both.
function sumOfMinMax(a, k) { const maxDq = [], minDq = []; let sum = 0; for (let i = 0; i < a.length; i++) { while (maxDq.length && a[maxDq[maxDq.length - 1]] <= a[i]) maxDq.pop(); while (minDq.length && a[minDq[minDq.length - 1]] >= a[i]) minDq.pop(); maxDq.push(i); minDq.push(i); if (maxDq[0] <= i - k) maxDq.shift(); if (minDq[0] <= i - k) minDq.shift(); if (i >= k - 1) sum += a[maxDq[0]] + a[minDq[0]]; } return sum;}