Maximum and Minimum Sums of at Most Size K Subarrays - Solution & Explanation

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.