We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum and Minimum Sums of at Most Size K Subsequences

Number: 3714

Difficulty: Medium

Paid? No

Companies: Meta

Problem Description

Given an integer array nums and a positive integer k, you need to compute the total sum (modulo 10⁹+7) of the maximum and minimum elements for every subsequence of nums that contains at most k elements. (Note that a subsequence has elements in the original order; its size can range from 1 up to k.) For example, if a subsequence consists of a single element x then its minimum and maximum are both x and contribute 2*x to the total.

Key Insights

  • Sorting the array helps in efficiently determining the number of times an element appears as the maximum or minimum in any valid subsequence.
  • When the array is sorted, if an element at index i is chosen as the maximum, then any subset of elements chosen from the indices [0, i-1] (using up to k-1 additional elements) can form a subsequence.
  • Similarly, if an element is chosen as the minimum, other elements must be chosen from the indices [i+1, n-1].
  • The small bound on k (at most 70) allows us to sum combination values for each element in O(k) per element.
  • Using precomputed factorials and inverse factorials, we can calculate binomial coefficients quickly without iterating fully over n.

Space and Time Complexity

Time Complexity: O(n * k) where n is the number of elements and k is at most 70. Space Complexity: O(n) for storing precomputed factorials and inverse factorials (plus additional O(n) space for sorting).

Solution

We first sort the input array. For each element in its sorted order:

  1. Compute the number of valid subsequences in which the element acts as the maximum. For an element at index i, you can choose any j (from 0 to min(k-1, i)) other elements from the first i elements (via C(i, j)).
  2. Compute the number of valid subsequences in which that same element acts as the minimum. For an element at index i, choose up to k-1 elements from the remaining n-i-1 elements (via C(n-i-1, j)).
  3. Multiply the element’s value by the sum of the two counts (each subsequence contributes the element’s value either as minimum or maximum; note that single element subsequences are counted twice).
  4. Sum these contributions modulo 10⁹+7.

Precomputing factorials and their modular inverses enables fast computation of the combination (binomial coefficient) C(n, r). Finally, we sum the contributions for all elements to obtain the answer.

Code Solutions

# Python solution with line-by-line comments
MOD = 10**9 + 7

def precompute_factorials(max_n, MOD):
    # Precompute factorials and inverse factorials up to max_n
    fact = [1] * (max_n + 1)
    inv_fact = [1] * (max_n + 1)
    for i in range(2, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD)
    for i in range(max_n, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % MOD
    return fact, inv_fact

def nCr(n, r, fact, inv_fact):
    if r < 0 or r > n:
        return 0
    return (fact[n] * inv_fact[r] % MOD) * inv_fact[n - r] % MOD

def maxMinSubseqSum(nums, k):
    n = len(nums)
    nums.sort()  # sort the array for easier combination calculations
    max_k = k  # we need to consider up to k-1 additional elements
    # We only need to compute factorials up to n.
    fact, inv_fact = precompute_factorials(n, MOD)
    
    total_sum = 0
    for i in range(n):
        val = nums[i]
        # Count how many times this element appears as maximum.
        max_count = 0
        # We can choose j additional elements from [0, i-1] for j from 0 to min(k-1, i)
        upper_bound = min(k-1, i)
        for j in range(0, upper_bound + 1):
            max_count = (max_count + nCr(i, j, fact, inv_fact)) % MOD
        
        # Count how many times this element appears as minimum.
        min_count = 0
        # Choose j elements from [i+1, n-1] for j from 0 to min(k-1, n-i-1)
        upper_bound = min(k-1, n - i - 1)
        for j in range(0, upper_bound + 1):
            min_count = (min_count + nCr(n - i - 1, j, fact, inv_fact)) % MOD
        
        # The element contributes its value times (times as max + times as min)
        total_sum = (total_sum + val * (max_count + min_count)) % MOD
    
    return total_sum

# Example usage:
#print(maxMinSubseqSum([1,2,3], 2))  # Expected output: 24
← Back to All Questions