Maximum and Minimum Sums of at Most Size K Subsequences solution and explanation
4 more videos on this problem
3428. Maximum and Minimum Sums of at Most Size K Subsequences | nCr | P&CAryan Mittal · 13:46 · 6K views
3428. Maximum and Minimum Sums of at Most Size K Subsequences (Leetcode Medium)Programming Live with Larry · 25:56 · 864 views
3428. Maximum and Minimum Sums of at Most Size K Subsequences | Sorting | Combination | nCrLeet's Code · 17:19 · 638 views
Maximum and Minimum Sums of at Most Size K Subsequences (Leetcode Weekly 433)Soumya Bhattacharjee · 5:50 · 285 views
【每日一题】LeetCode 3428. Maximum and Minimum Sums of at Most Size K SubsequencesHuifeng Guan · 26:30 · 271 views
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 subsequences of nums with at most k elements.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3], k = 2
Output: 24
Explanation:
The subsequences of nums with at most 2 elements are:
| Subsequence | Minimum | Maximum | Sum |
|---|---|---|---|
[1] |
1 | 1 | 2 |
[2] |
2 | 2 | 4 |
[3] |
3 | 3 | 6 |
[1, 2] |
1 | 2 | 3 |
[1, 3] |
1 | 3 | 4 |
[2, 3] |
2 | 3 | 5 |
| Final Total | 24 |
The output would be 24.
Example 2:
Input: nums = [5,0,6], k = 1
Output: 22
Explanation:
For subsequences with exactly 1 element, the minimum and maximum values are the element itself. Therefore, the total is 5 + 5 + 0 + 0 + 6 + 6 = 22.
Example 3:
Input: nums = [1,1,1], k = 2
Output: 12
Explanation:
The subsequences [1, 1] and [1] each appear 3 times. For all of them, the minimum and maximum are both 1. Thus, the total is 12.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1091 <= k <= min(70, nums.length)
Approach overview
Problem Overview: You receive an integer array and an integer k. Consider every subsequence whose size is at most k. For each subsequence, identify its minimum and maximum element, then accumulate their contributions across all valid subsequences. The goal is to compute the total efficiently without explicitly generating every subsequence.
Approach 1: Brute Force Enumeration (O(2^n * n) time, O(n) space)
The most direct idea is to generate every subsequence using bitmasks or backtracking. For each subsequence, check if its size is ≤ k, then scan the elements to compute the minimum and maximum. Add both values to the running total. This approach is easy to implement but explodes combinatorially because an array of size n has 2^n subsequences. Even moderate input sizes make this impractical, but it helps clarify how minimum and maximum values contribute to the final sum.
Approach 2: Sorting + Combinatorics Contribution Counting (O(n log n + nk) time, O(n) space)
The key observation: instead of enumerating subsequences, count how many subsequences treat a specific element as their minimum or maximum. Start by sorting the array using techniques from sorting. When the array is sorted, elements to the left are smaller and elements to the right are larger. This ordering makes it easy to determine how many subsequences can choose the current element as their minimum or maximum.
For an element at index i, treat it as the maximum. You can choose up to k-1 additional elements from the i elements before it. The number of such subsequences equals the sum of combinations C(i, t) for t = 0..k-1. Similarly, treat the element as the minimum and select up to k-1 elements from the right side. Precompute combinations using techniques from combinatorics or dynamic programming so each query is constant time. Multiply the element value by the number of subsequences where it acts as min or max, and accumulate the contribution.
This transforms an exponential enumeration problem into a counting problem. Instead of building subsequences, you iterate through the array once and use combinatorial counts to measure how often each value participates.
Approach 3: Dynamic Programming for Combination Prefix Sums (O(nk) time, O(nk) space)
If combination values are needed frequently, precompute C(n, r) using a Pascal triangle style dynamic programming table. Build combination values up to n and k, then maintain prefix sums of combinations so the number of ways to choose ≤ k-1 elements can be retrieved quickly. This reduces repeated summation when calculating contributions for each index. The overall logic stays the same: count subsequences where each element becomes the minimum or maximum.
Recommended for interviews: The sorting + combinatorics contribution approach is what interviewers expect. Brute force shows understanding of the subsequence definition, but recognizing that each element's contribution can be counted with combinations demonstrates stronger algorithmic insight and familiarity with counting techniques.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Enumeration | O(2^n * n) | O(n) | Small arrays or when demonstrating the baseline idea during interviews |
| Sorting + Combinatorics Contribution Counting | O(n log n + nk) | O(n) | General optimal solution when counting how often elements appear as min or max |
| Dynamic Programming Combination Table | O(nk) | O(nk) | When many combination queries are needed and precomputation simplifies counting |
Frequently asked questions
Is Maximum and Minimum Sums of at Most Size K Subsequences easy or hard?
LeetCode classifies this problem as Medium, but it can feel closer to hard if you are unfamiliar with contribution counting or combinatorics. The main difficulty is recognizing that enumerating subsequences is unnecessary once you count how often each element becomes the minimum or maximum.
Maximum and Minimum Sums of at Most Size K Subsequences Python/Java solution
Implementations in Python, Java, C++, and Go follow the same structure: sort the array, precompute combinations C(n, r), and iterate through each index to calculate how many subsequences use that value as minimum or maximum. Multiply the value by its count and accumulate the result using modular arithmetic if required.
How to solve Maximum and Minimum Sums of at Most Size K Subsequences in O(n log n)?
Sort the array and treat each element as a candidate minimum and maximum. For index i as the maximum, count subsequences formed by choosing up to k-1 elements from the i elements before it. For the minimum case, choose elements from the right side. Use precomputed combination values to calculate these counts efficiently and multiply by the element value to accumulate the contribution.
What is the best approach for Maximum and Minimum Sums of at Most Size K Subsequences?
The most efficient solution sorts the array and counts how many subsequences treat each element as the minimum or maximum. Instead of generating subsequences, you use combinatorics to compute how many ways to choose up to k-1 additional elements around a fixed value. This reduces the problem to O(n log n + nk) time after sorting and combination precomputation.
Is Maximum and Minimum Sums of at Most Size K Subsequences asked at Google/Amazon/Meta?
Problems involving subsequence counting, combinatorics, and contribution techniques frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require counting how often elements act as minimum or maximum are common in algorithm interviews focused on arrays and combinatorics.
What data structure is used in Maximum and Minimum Sums of at Most Size K Subsequences?
The solution primarily uses arrays along with combinatorics tables or prefix sums for combination values. Sorting is required to order elements so the number of smaller and larger choices can be determined efficiently.
What is the time complexity of Maximum and Minimum Sums of at Most Size K Subsequences?
The optimal approach runs in O(n log n + nk) time. Sorting the array takes O(n log n), and computing contribution counts for each element requires combination calculations up to k. Space complexity is typically O(n) or O(nk) depending on how combinations are stored.