Skip to main content
Talentd

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

HardArrayMathStackMonotonic Stack5 min read
Practice this problem

Problem Statement

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
  • -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

Code

JavaScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray EnumerationO(n²)O(1)Small arrays or when building intuition about subarray min/max behavior
Monotonic Stack Contribution CountingO(n)O(n)General case and interview solution; handles large inputs efficiently

Video Solution

Maximum and Minimum Sums of at Most Size K Subarrays (Leetcode Weekly 433) • Soumya Bhattacharjee • 684 views views

Watch 3 more video solutions →

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.

Ready to solve this problem?

Practice Maximum and Minimum Sums of at Most Size K Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Next Greater Element II