Maximum and Minimum Sums of at Most Size K Subsequences

Maximum and Minimum Sums of at Most Size K Subsequences - 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 10⁹ + 7.

Note: A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1], k = 1

› Output: 6

💡 Note: Subsequences of size ≤ 1: [2] gives 2+2=4, [1] gives 1+1=2. Total: 4+2=6

Example 2 — Multiple Sizes

$ Input: nums = [1,3,2], k = 2

› Output: 24

💡 Note: Size 1: [1]→2, [3]→6, [2]→4. Size 2: [1,3]→4, [1,2]→3, [3,2]→5. Total: 2+6+4+4+3+5=24

Example 3 — Edge Case

$ Input: nums = [5], k = 1

› Output: 10

💡 Note: Only one subsequence [5], max=5, min=5, so 5+5=10

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ k ≤ nums.length
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,2] and k=2

Process

Generate all subsequences ≤ size k and find max+min

Output

Sum all (max+min) values

Key Takeaway

🎯 Key Insight: Each element contributes predictably as max/min based on its position in sorted order

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to use combinatorics after sorting to count how many times each element appears as maximum or minimum in subsequences. The brute force approach generates all subsequences (exponential time), while the optimal approach sorts the array and mathematically calculates each element's contribution. Best approach is sort and count with Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Count Contributions	O(n log n + n²)	O(1)	Sort array and count how many times each element appears as max/min
Generate All Subsequences	O(2ⁿ × n)	O(n)	Generate all possible subsequences and sum their max + min values

Sort and Count Contributions — Algorithm Steps

Sort the array to determine relative ordering
For each element, calculate in how many subsequences it's the maximum
For each element, calculate in how many subsequences it's the minimum
Sum all contributions and return modulo 10^9 + 7

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort array to establish ordering

Calculate

Count max/min contributions using combinatorics

Sum

Add weighted contributions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MOD = 1000000007;

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

long long pow_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

long long comb(long long* fact, int n, int r) {
    if (r > n || r < 0) return 0;
    return (fact[n] * pow_mod(fact[r] * fact[n-r] % MOD, MOD-2, MOD)) % MOD;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), compare);
    
    // Precompute factorials
    long long fact[numsSize + 1];
    fact[0] = 1;
    for (int i = 1; i <= numsSize; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    
    long long total = 0;
    
    for (int i = 0; i < numsSize; i++) {
        // Count subsequences where nums[i] is maximum
        long long maxContrib = 0;
        for (int size = 1; size <= min(k, i + 1); size++) {
            if (size - 1 <= i) {
                maxContrib = (maxContrib + comb(fact, i, size - 1)) % MOD;
            }
        }
        
        // Count subsequences where nums[i] is minimum
        long long minContrib = 0;
        for (int size = 1; size <= min(k, numsSize - i); size++) {
            if (size - 1 <= numsSize - i - 1) {
                minContrib = (minContrib + comb(fact, numsSize - i - 1, size - 1)) % MOD;
            }
        }
        
        total = (total + (long long)nums[i] * (maxContrib + minContrib)) % MOD;
    }
    
    return (int) total;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + n²)

Sorting takes O(n log n), then O(n²) for combinatorial calculations

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for calculations

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

420 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Count Contributions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler