Scale Engineer

Maximum and Minimum Sums of at Most Size K Subsequences

Med
#3046Time: O(k * 2^n). There are `2^n` subsequences. For each valid one, we iterate up to `k` elements to find the min and max.Space: O(n * 2^n) if storing all subsequences, or O(n) for recursion depth if processing on-the-fly.
Patterns
MathDynamic ProgrammingCombinatorics
Algorithms
Sorting
Data structures
Array

Prompt

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 <= 105
  • 0 <= nums[i] <= 109
  • 1 <= k <= min(70, nums.length)

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating all possible non-empty subsequences of the input array nums. For each generated subsequence, we check if its size is at most k. If it is, we find its minimum and maximum elements and add their sum to a running total. This is the most straightforward but also the most inefficient way to solve the problem.

Algorithm

  • Initialize a global variable totalSum to 0.
  • Define a recursive function, say generate(index, currentSubsequence), to generate all subsequences.
  • The base case for the recursion is when index reaches the end of the nums array.
  • In the base case, if the currentSubsequence is not empty, it represents one of the 2^n possible subsequences. Add it to a list of all subsequences.
  • The recursive step involves two calls:
    1. One that excludes nums[index] from the subsequence: generate(index + 1, currentSubsequence).
    2. One that includes nums[index]: currentSubsequence.add(nums[index]); generate(index + 1, currentSubsequence); followed by backtracking.
  • After generating all subsequences, iterate through them.
  • For each subsequence, if its size is greater than 0 and at most k, find its minimum and maximum elements.
  • Add the sum of the minimum and maximum to totalSum, taking the result modulo 10^9 + 7.
  • Return the final totalSum.

Walkthrough

We can implement this using a recursive helper function. The function explores two choices for each element in nums: either include it in the current subsequence or not. This process naturally generates all 2^n subsequences. Once a subsequence is formed (when the recursion reaches the end of the array), we check if it meets the size criteria (1 <= size <= k). If it does, we compute its minimum and maximum values and add them to a global sum. All additions are performed modulo 10^9 + 7.

class Solution {    long totalSum = 0;    int MOD = 1_000_000_007;     public int maximumMinimumSum(int[] nums, int k) {        // This conceptual brute-force approach will time out.        List<List<Integer>> allSubsequences = new ArrayList<>();        generateSubsequences(nums, 0, new ArrayList<>(), allSubsequences);                for (List<Integer> sub : allSubsequences) {            if (sub.size() > 0 && sub.size() <= k) {                long minVal = Long.MAX_VALUE, maxVal = Long.MIN_VALUE;                for (int val : sub) {                    minVal = Math.min(minVal, val);                    maxVal = Math.max(maxVal, val);                }                totalSum = (totalSum + minVal + maxVal) % MOD;            }        }        return (int) totalSum;    }     private void generateSubsequences(int[] nums, int index, List<Integer> current, List<List<Integer>> allSubsequences) {        if (index == nums.length) {            allSubsequences.add(new ArrayList<>(current));            return;        }        // Exclude nums[index]        generateSubsequences(nums, index + 1, current, allSubsequences);        // Include nums[index]        current.add(nums[index]);        generateSubsequences(nums, index + 1, current, allSubsequences);        current.remove(current.size() - 1); // Backtrack    }}

Complexity

Time

O(k * 2^n). There are `2^n` subsequences. For each valid one, we iterate up to `k` elements to find the min and max.

Space

O(n * 2^n) if storing all subsequences, or O(n) for recursion depth if processing on-the-fly.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for very small input sizes.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will cause a Time Limit Exceeded (TLE) error for constraints where n is larger than about 20.

  • May also lead to Memory Limit Exceeded (MLE) if all subsequences are stored.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem