Maximum and Minimum Sums of at Most Size K Subarrays

Hard

#3048Time: O(n * k), where `n` is the number of elements in `nums`. The outer loop runs `n` times, and the inner loop runs at most `k` times. Inside the inner loop, operations are O(1).Space: O(1) extra space, as we only use a few variables to store the running sum and current min/max.

Patterns

Math

Data structures

Array Stack Monotonic Stack

Prompt

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 <= 80000
1 <= k <= nums.length
-10⁶ <= nums[i] <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through all possible subarrays that satisfy the length constraint (at most k). For each starting position i, we extend the subarray to the right, one element at a time, up to a length of k. While extending, we keep track of the minimum and maximum values seen so far in the current subarray and add them to a running total.

Algorithm

Initialize a variable totalSum to 0.
Use a nested loop to generate all subarrays. The outer loop iterates from i = 0 to n-1 to select the starting index of the subarray.
The inner loop iterates from j = i to n-1 to select the ending index.
Inside the inner loop, check if the length of the current subarray (j - i + 1) is greater than k. If it is, break the inner loop as subsequent subarrays starting at i will also be too long.
For each valid subarray nums[i..j], we need to find its minimum and maximum elements. Instead of re-calculating this from scratch for each subarray, we can maintain the minimum and maximum of the subarray nums[i..j] as we extend it from j to j+1.
For a fixed i, initialize currentMin = nums[i] and currentMax = nums[i].
As j increases, update currentMin = min(currentMin, nums[j]) and currentMax = max(currentMax, nums[j]).
Add the currentMin and currentMax to totalSum.
After iterating through all possible subarrays, return totalSum.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. We generate every single subarray, check if its length is at most k, and if so, find its minimum and maximum elements to add to our total sum.

A slight optimization on the naive brute-force method is to avoid re-calculating the minimum and maximum for each subarray. When we consider subarrays starting at index i, we can iterate with a second pointer j from i outwards. As we expand the subarray nums[i..j] by incrementing j, we can update the minimum and maximum in O(1) time.

1class Solution {2    public long findMaximumsAndMinimums(int[] nums, int k) {3        long totalSum = 0;4        int n = nums.length;5 6        for (int i = 0; i < n; i++) {7            int currentMin = Integer.MAX_VALUE;8            int currentMax = Integer.MIN_VALUE;9            // Iterate through all subarrays starting at i with length at most k10            for (int j = i; j < n && (j - i + 1) <= k; j++) {11                // Update min and max for the subarray nums[i..j]12                currentMin = Math.min(currentMin, nums[j]);13                currentMax = Math.max(currentMax, nums[j]);14                15                // Add the min and max of the current subarray to the total sum16                totalSum += (long)currentMin + currentMax;17            }18        }19 20        return totalSum;21    }22}

Complexity

Time

O(n * k), where `n` is the number of elements in `nums`. The outer loop runs `n` times, and the inner loop runs at most `k` times. Inside the inner loop, operations are O(1).

Space

O(1) extra space, as we only use a few variables to store the running sum and current min/max.

Trade-offs

Pros

Simple to understand and implement.
Uses constant extra space.

Cons

The time complexity of O(n*k) is too slow for the given constraints, where n and k can be up to 80,000. This will result in a Time Limit Exceeded (TLE) error on most platforms.

A much more efficient approach is to change perspective. Instead of iterating through subarrays, we can iterate through each element nums[i] and calculate its total contribution to the final sum. The problem can be split into two parts: finding the sum of all maximums and the sum of all minimums. The logic is symmetrical, so we'll focus on the maximums.

The contribution of nums[i] to the sum of maximums is nums[i] multiplied by the number of subarrays (of length at most k) in which nums[i] is the maximum element. We can use a monotonic stack to efficiently find the nearest elements to the left and right of i that are larger than nums[i]. This defines a range where nums[i] is the maximum. Within this range, we can then use a mathematical formula to count how many subarrays satisfy the length constraint k in O(1) time. This leads to an overall linear time solution.

Algorithm

Decompose the problem into two independent subproblems: calculating the sum of maximums of all valid subarrays, and the sum of minimums of all valid subarrays. The final answer is the sum of these two results.
Let's focus on the sum of maximums. Instead of iterating over subarrays, we iterate through each element nums[i] and calculate its total contribution. The contribution of nums[i] is nums[i] multiplied by the number of valid subarrays for which nums[i] is the maximum.
To count these subarrays, we first need to find the range (L, R) in which nums[i] is the maximum. L is the index of the first element to the left of i that is greater than nums[i], and R is the index of the first element to the right of i that is greater than or equal to nums[i]. This specific tie-breaking (using > on one side and >= on the other) ensures that for any subarray, the maximum element is counted exactly once. These L and R boundaries can be found for all i in O(n) time using a monotonic stack.
For a fixed i, nums[i] is the maximum for any subarray nums[l..r] where L < l <= i and i <= r < R. We also have the constraint that the subarray length r - l + 1 <= k.
Let x = i - L and y = R - i. These are the number of possible start positions (relative to i) and end positions, respectively. We need to count pairs of (l, r) satisfying the conditions. This can be formulated as a counting problem that can be solved with a derived mathematical formula in O(1) time for each i.
The number of valid subarrays for nums[i] as max is count = sum_{p=0 to x-1} (min(y, k-p)). This sum can be calculated in O(1) by splitting it into two parts: one where k-p >= y and one where k-p < y.
Sum up the contributions nums[i] * count for all i to get the total sum of maximums.
Repeat a symmetrical process for the sum of minimums (e.g., finding next smaller elements) and add the results.

Walkthrough

This approach hinges on calculating the contribution of each element nums[i] separately for the sum of maximums and the sum of minimums.

Let's define a helper function calculateContribution(nums, k, isMax).

1. Finding Boundaries with a Monotonic Stack: To find the number of subarrays where nums[i] is the maximum, we need to find its effective range. We find left[i], the index of the first element to the left of i that is strictly greater than nums[i], and right[i], the index of the first element to the right that is greater than or equal to nums[i]. This can be done for all i in O(n) using a monotonic decreasing stack. A similar process with a monotonic increasing stack is used for minimums.

2. Calculating Contribution: Once we have left[i] and right[i], we know that nums[i] is the maximum for any subarray nums[l..r] where left[i] < l <= i and i <= r < right[i]. Let x = i - left[i] be the number of possible start positions to the left (including i) and y = right[i] - i be the number of possible end positions to the right (including i).

We now need to count the pairs (l, r) that also satisfy r - l + 1 <= k. This can be done with an O(1) formula derived from summing up the possibilities. For each possible number of elements to the left of i, p (from 0 to x-1), we count the valid number of elements to the right, q (from 0 to y-1), such that p + q + 1 <= k. The total count for nums[i] is sum_{p=0 to x-1} min(y, k-p). This sum can be computed in O(1) by splitting it into an arithmetic series and a constant part.

3. Final Sum: The final answer is calculateContribution(nums, k, true) + calculateContribution(nums, k, false).

1import java.util.ArrayDeque;2import java.util.Deque;3 4class Solution {5    public long findMaximumsAndMinimums(int[] nums, int k) {6        long sumMax = calculateContribution(nums, k, true);7        long sumMin = calculateContribution(nums, k, false);8        return sumMax + sumMin;9    }10 11    private long calculateContribution(int[] nums, int k, boolean isMax) {12        int n = nums.length;13        int[] left = new int[n];14        Deque<Integer> stack = new ArrayDeque<>();15 16        // To ensure each subarray's max/min is counted once, we use a strict inequality17        // on one side and a non-strict one on the other for tie-breaking.18        // For max: left is next >, right is next >=.19        // For min: left is next <, right is next <=.20 21        // Left boundary (strict)22        for (int i = 0; i < n; i++) {23            while (!stack.isEmpty() && 24                   (isMax ? nums[stack.peek()] <= nums[i] : nums[stack.peek()] >= nums[i])) {25                stack.pop();26            }27            left[i] = stack.isEmpty() ? -1 : stack.peek();28            stack.push(i);29        }30 31        int[] right = new int[n];32        stack.clear();33 34        // Right boundary (non-strict)35        for (int i = n - 1; i >= 0; i--) {36            while (!stack.isEmpty() && 37                   (isMax ? nums[stack.peek()] < nums[i] : nums[stack.peek()] > nums[i])) {38                stack.pop();39            }40            right[i] = stack.isEmpty() ? n : stack.peek();41            stack.push(i);42        }43 44        long totalContribution = 0;45        for (int i = 0; i < n; i++) {46            long x = i - left[i];47            long y = right[i] - i;48 49            // Count valid subarrays where nums[i] is the extremum.50            // This is equivalent to counting pairs (p, q) where 0<=p<x, 0<=q<y and p+q+1 <= k.51            // The formula is: sum_{p=0 to x-1} min(y, k-p)52            long count = 0;53            long p_split = k - y;54 55            if (p_split >= x) { // k >= x+y, all x*y subarrays are valid56                count = x * y;57            } else {58                // Part 1: p from 0 to p_split-1. Here, k-p > y, so min(y, k-p) = y.59                if (p_split > 0) {60                    count += p_split * y;61                }62                // Part 2: p from max(0, p_split) to x-1. Here, k-p <= y, so min(y, k-p) = k-p.63                // This is an arithmetic series sum.64                long start_p = Math.max(0, p_split);65                long num_terms = x - start_p;66                if (num_terms > 0) {67                    long first_term = k - start_p;68                    long last_term = k - (x - 1);69                    count += num_terms * (first_term + last_term) / 2;70                }71            }72            totalContribution += (long)nums[i] * count;73        }74        return totalContribution;75    }76}

Complexity

Time

O(n). Finding the left and right boundaries for all elements using a monotonic stack takes O(n). The final loop to calculate contributions also runs `n` times, with O(1) work inside. Thus, the total time complexity is linear.

Space

O(n) to store the `left` and `right` boundary arrays and for the stack used in their computation.

Trade-offs

Pros

Highly efficient with a linear time complexity, making it suitable for large inputs.
The core logic of contribution and monotonic stacks is a powerful pattern applicable to many other problems.

Cons

The logic is significantly more complex than the brute-force approach.
The implementation requires careful handling of edge cases and the logic for counting subarrays, which can be error-prone.
Requires O(n) extra space for stacks and boundary arrays.

Solutions

Solution

1/** * @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 ; };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem