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.

Description Hints 3 Solution Video 16:59

3430. Maximum and Minimum Sums of at Most Size K Subarrays

Hard25.9% acceptance

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⁶

Topics

Hints open one at a time

Hint 1

Use a monotonic stack.

Hint 2

How can we calculate the number of subarrays where an element is the largest?

Hint 3

Enforce the condition on size too.

16:59

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

3430. Maximum and Minimum Sums of at Most Size K Subarrays

Topics

Hints open one at a time

Similar problems