Maximum and Minimum Sums of at Most Size K Subarrays solution and explanation
3 more videos on this problem
Maximum and Minimum Sums of at Most Size K Subarrays (Leetcode Weekly 433)Soumya Bhattacharjee · 16:59 · 684 views
3430. Maximum and Minimum Sums of at Most Size K Subarrays (Leetcode Hard)Programming Live with Larry · 1:27:06 · 642 views
3430 Maximum and Minimum Sums of at Most Size K Subarray (LeetCode Hard)WYCode · 14:24 · 298 views
Maximum and Minimum Sums of at Most Size K Subarrays LeetCodealgorithmswala · 3:31
The problem
You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subarrays with at most k elements.
Example 1:
Input: nums = [1,2,3], k = 2
Output: 20
Explanation:
The subarrays of nums with at most 2 elements are:
| Subarray | Minimum | Maximum | Sum |
|---|---|---|---|
[1] |
1 | 1 | 2 |
[2] |
2 | 2 | 4 |
[3] |
3 | 3 | 6 |
[1, 2] |
1 | 2 | 3 |
[2, 3] |
2 | 3 | 5 |
| Final Total | 20 |
The output would be 20.
Example 2:
Input: nums = [1,-3,1], k = 2
Output: -6
Explanation:
The subarrays of nums with at most 2 elements are:
| Subarray | Minimum | Maximum | Sum |
|---|---|---|---|
[1] |
1 | 1 | 2 |
[-3] |
-3 | -3 | -6 |
[1] |
1 | 1 | 2 |
[1, -3] |
-3 | 1 | -2 |
[-3, 1] |
-3 | 1 | -2 |
| Final Total | -6 |
The output would be -6.
Constraints:
1 <= nums.length <= 800001 <= k <= nums.length-106 <= nums[i] <= 106
Approach overview
Problem Overview: Given an array nums and an integer k, compute the sum of the maximum and minimum values across every subarray whose length is at most k. The challenge is efficiently counting how many valid subarrays treat each element as the minimum or maximum.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Generate every subarray starting at index i and extend it up to length k. While expanding the window, maintain the current minimum and maximum values. For each valid subarray, add min + max to the answer. This approach directly follows the problem definition but checks up to k elements for every start index, resulting in quadratic behavior when k approaches n. Useful for understanding the problem mechanics but not scalable.
Approach 2: Monotonic Stack Contribution Counting (O(n) time, O(n) space)
Instead of enumerating subarrays, count how many subarrays treat each element as the minimum and how many treat it as the maximum. Use a monotonic stack to find the nearest smaller/greater elements on both sides. These boundaries determine the span where the element remains the dominant minimum or maximum.
For an index i, compute left choices and right choices for extending the subarray while keeping nums[i] as the min or max. Normally this gives left * right subarrays, but the length constraint l + r - 1 ≤ k must also hold. Clamp both sides to k and count valid pairs using simple arithmetic. Multiply the number of valid subarrays by nums[i] to accumulate its contribution. Run this process once for minimums and once for maximums.
This technique relies on properties of stack-based boundary discovery and a bit of math to count valid subarray lengths without enumeration. Each element is pushed and popped at most once, so the algorithm runs in linear time.
Recommended for interviews: The monotonic stack contribution approach. Interviewers expect you to recognize the pattern used in problems like "Sum of Subarray Minimums" or "Sum of Subarray Ranges". Starting with brute force shows you understand the requirement, but deriving the O(n) stack-based counting demonstrates strong algorithmic intuition.
Solution
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minMaxSubarraySum = function (nums, k) {
const computeSum = (nums, k, isMin) => {
const n = nums.length;
const prev = Array(n).fill(-1);
const next = Array(n).fill(n);
let stk = [];
if (isMin) {
for (let i = 0; i < n; i++) {
while (stk.length > 0 && nums[stk[stk.length - 1]] >= nums[i]) {
stk.pop();
}
prev[i] = stk.length > 0 ? stk[stk.length - 1] : -1;
stk.push(i);
}
stk = [];
for (let i = n - 1; i >= 0; i--) {
while (stk.length > 0 && nums[stk[stk.length - 1]] > nums[i]) {
stk.pop();
}
next[i] = stk.length > 0 ? stk[stk.length - 1] : n;
stk.push(i);
}
} else {
for (let i = 0; i < n; i++) {
while (stk.length > 0 && nums[stk[stk.length - 1]] <= nums[i]) {
stk.pop();
}
prev[i] = stk.length > 0 ? stk[stk.length - 1] : -1;
stk.push(i);
}
stk = [];
for (let i = n - 1; i >= 0; i--) {
while (stk.length > 0 && nums[stk[stk.length - 1]] < nums[i]) {
stk.pop();
}
next[i] = stk.length > 0 ? stk[stk.length - 1] : n;
stk.push(i);
}
}
let totalSum = 0;
for (let i = 0; i < n; i++) {
const left = prev[i];
const right = next[i];
const a = left + 1;
const b = i;
const c = i;
const d = right - 1;
let start1 = Math.max(a, i - k + 1);
let endCandidate1 = d - k + 1;
let upper1 = Math.min(b, endCandidate1);
let sum1 = 0;
if (upper1 >= start1) {
const termCount = upper1 - start1 + 1;
const first = start1;
const last = upper1;
const indexSum = (last * (last + 1)) / 2 - ((first - 1) * first) / 2;
const constantSum = (k - i) * termCount;
sum1 = indexSum + constantSum;
}
let start2 = upper1 + 1;
let end2 = b;
start2 = Math.max(start2, a);
end2 = Math.min(end2, b);
let sum2 = 0;
if (start2 <= end2) {
const count = end2 - start2 + 1;
const term = d - i + 1;
sum2 = term * count;
}
totalSum += nums[i] * (sum1 + sum2);
}
return totalSum;
};
const minSum = computeSum(nums, k, true);
const maxSum = computeSum(nums, k, false);
return minSum + maxSum;
};Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n²) | O(1) | Small arrays or when building intuition about subarray min/max behavior |
| Monotonic Stack Contribution Counting | O(n) | O(n) | General case and interview solution; handles large inputs efficiently |
Frequently asked questions
Is Maximum and Minimum Sums of at Most Size K Subarrays easy or hard?
This problem is considered Hard because it combines monotonic stack boundaries with constrained subarray counting. Recognizing the contribution technique and correctly applying the length ≤ k restriction requires strong experience with stack-based array algorithms.
Maximum and Minimum Sums of at Most Size K Subarrays Python/Java solution
The standard implementation uses monotonic stacks and contribution counting. The same algorithm works across Python, Java, C++, Go, and JavaScript: compute boundaries with stacks, count valid subarrays respecting the ≤ k constraint, and accumulate minimum and maximum contributions separately.
How to solve Maximum and Minimum Sums of at Most Size K Subarrays in O(n)?
Compute how many subarrays treat each element as the minimum and maximum using monotonic stacks. Determine the distance to the previous and next smaller or greater elements, which defines the span where the element dominates. Use arithmetic counting to restrict valid subarrays to length ≤ k, then accumulate the element's contribution. The stack ensures linear processing across the array.
What is the best approach for Maximum and Minimum Sums of at Most Size K Subarrays?
The most efficient approach uses a monotonic stack to compute each element's contribution as both a minimum and a maximum. By finding the previous and next boundaries where the element stops being dominant, you can count how many subarrays include it while respecting the length constraint ≤ k. This reduces the complexity to O(n) time with O(n) extra space.
Is Maximum and Minimum Sums of at Most Size K Subarrays asked at Google/Amazon/Meta?
Problems involving monotonic stacks and subarray contribution counting frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as Sum of Subarray Minimums, Subarray Ranges, and maximum contribution problems test the same pattern used in this problem.
What data structure is used in Maximum and Minimum Sums of at Most Size K Subarrays?
The core data structure is a monotonic stack. It helps find the nearest smaller or greater elements on each side of every index in O(n) time. This boundary information allows efficient counting of subarrays where a value acts as the minimum or maximum.
What is the time complexity of Maximum and Minimum Sums of at Most Size K Subarrays?
The optimal monotonic stack solution runs in O(n) time because each array element is pushed and popped from the stack at most once. Space complexity is O(n) for storing stack indices and boundary arrays. A brute force method that enumerates subarrays takes O(n²) time.