3428. Maximum and Minimum Sums of at Most Size K Subsequences LeetCode Solution
In this guide, you will get 3428. Maximum and Minimum Sums of at Most Size K Subsequences LeetCode Solution with the best time and space complexity. The solution to Maximum and Minimum Sums of at Most Size K Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum and Minimum Sums of at Most Size K Subsequences
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.
3428. Maximum and Minimum Sums of at Most Size K Subsequences LeetCode Solution in C++
class Solution {
public:
int minMaxSums(vector<int>& nums, int k) {
// In a sorted array, nums[i] will be
// 1. The maximum for subsequences formed by nums[0..i].
// 2. The minimum for subsequences formed by nums[i..n - 1].
//
// The number of times nums[i] is the maximum is the same as the number of
// times nums[n - 1 - i] is the minimum, due to the symmetry in subsequences
// derived from the sorted order.
//
// To calculate the contribution of nums[i], we need to find the number of
// ways to select at most (k - 1) elements from the range of indices where
// nums[i] is the smallest or nums[n - 1 - i] is the largest.
const int n = nums.size();
const vector<vector<int>> comb = getComb(n, k - 1);
long ans = 0;
ranges::sort(nums);
// i := available numbers from the left of nums[i] or
// available numbers from the right of nums[n - 1 - i]
for (int i = 0; i < n; ++i) {
int count = 0;
for (int j = 0; j <= k - 1; ++j) // selected numbers
count = (count + comb[i][j]) % kMod;
ans += static_cast<long>(nums[i]) * count;
ans += static_cast<long>(nums[n - 1 - i]) * count;
ans %= kMod;
}
return ans;
}
private:
static constexpr int kMod = 1'000'000'007;
// C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
vector<vector<int>> getComb(int n, int k) {
vector<vector<int>> comb(n + 1, vector<int>(k + 1));
for (int i = 0; i <= n; ++i)
comb[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j)
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % kMod;
return comb;
}
}; /* code provided by PROGIEZ */
3428. Maximum and Minimum Sums of at Most Size K Subsequences LeetCode Solution in Java
class Solution {
public int minMaxSums(int[] nums, int k) {
// In a sorted array, nums[i] will be
// 1. The maximum for subsequences formed by nums[0..i].
// 2. The minimum for subsequences formed by nums[i..n - 1].
//
// The number of times nums[i] is the maximum is the same as the number of
// times nums[n - 1 - i] is the minimum, due to the symmetry in subsequences
// derived from the sorted order.
//
// To calculate the contribution of nums[i], we need to find the number of
// ways to select at most (k - 1) elements from the range of indices where
// nums[i] is the smallest or nums[n - 1 - i] is the largest.
final int n = nums.length;
final int[][] comb = getComb(n, k - 1);
long ans = 0;
Arrays.sort(nums);
// i: available numbers from the left of nums[i] or
// available numbers from the right of nums[n - 1 - i]
for (int i = 0; i < n; ++i) {
int count = 0;
for (int j = 0; j <= k - 1; ++j) // selected numbers
count = (count + comb[i][j]) % kMod;
ans += (long) nums[i] * count;
ans += (long) nums[n - 1 - i] * count;
ans %= kMod;
}
return (int) ans;
}
private static final int kMod = 1_000_000_007;
// C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
private int[][] getComb(int n, int k) {
int[][] comb = new int[n + 1][k + 1];
for (int i = 0; i <= n; ++i)
comb[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j)
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % kMod;
return comb;
}
} // code provided by PROGIEZ
3428. Maximum and Minimum Sums of at Most Size K Subsequences LeetCode Solution in Python
class Solution:
def minMaxSums(self, nums: list[int], k: int) -> int:
# In a sorted array, nums[i] will be
# 1. The maximum for subsequences formed by nums[0..i].
# 2. The minimum for subsequences formed by nums[i..n - 1].
#
# The number of times nums[i] is the maximum is the same as the number of
# times nums[n - 1 - i] is the minimum, due to the symmetry in subsequences
# derived from the sorted order.
#
# To calculate the contribution of nums[i], we need to find the number of
# ways to select at most (k - 1) elements from the range of indices where
# nums[i] is the smallest or nums[n - 1 - i] is the largest.
kMod = 1_000_000_007
n = len(nums)
def getComb(n: int, k: int) -> list[list[int]]:
"""C(n, k) = C(n - 1, k) + C(n - 1, k - 1)"""
comb = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(n + 1):
comb[i][0] = 1
for i in range(1, n + 1):
for j in range(1, k + 1):
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % kMod
return comb
comb = getComb(n, k - 1)
ans = 0
nums.sort()
# i: available numbers from the left of nums[i] or
# available numbers from the right of nums[-1 - i]
for i in range(n):
count = 0
for j in range(k): # selected numbers
count = (count + comb[i][j]) % kMod
ans += nums[i] * count
ans += nums[-1 - i] * count
ans %= kMod
return ans # code by PROGIEZ
