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.

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.

Description Hints 1 Video 13:46

3428. Maximum and Minimum Sums of at Most Size K Subsequences

Q: 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.

Medium21.7% acceptance3 companies

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 10⁹ + 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 <= 10⁵
0 <= nums[i] <= 10⁹
1 <= k <= min(70, nums.length)

Asked at 3 companies

Amazon Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Sort the array.

LanguageLoading editor…

1class Solution:
2    def minMaxSums(self, nums: List[int], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3]
2

Input

[5,0,6]
1

Input

[1,1,1]
2

Your code is saved on this device.