Sum of minimum and maximum of all subarrays of size k

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}