Find the K-Sum of an Array

HARD

Description

You are given an integer array nums and a positive integer k. You can choose any subsequence of the array and sum all of its elements together.

We define the K-Sum of the array as the k^th largest subsequence sum that can be obtained (not necessarily distinct).

Return the K-Sum of the array.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Note that the empty subsequence is considered to have a sum of 0.

Example 1:

Input: nums = [2,4,-2], k = 5
Output: 2
Explanation: All the possible subsequence sums that we can obtain are the following sorted in decreasing order:
- 6, 4, 4, 2, 2, 0, 0, -2.
The 5-Sum of the array is 2.

Example 2:

Input: nums = [1,-2,3,4,-10,12], k = 16
Output: 10
Explanation: The 16-Sum of the array is 10.

Constraints:

n == nums.length
1 <= n <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= k <= min(2000, 2ⁿ)

Approaches

Checkout 2 different approaches to solve Find the K-Sum of an Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Generate All Subsequence Sums

A naive but fundamental approach is to generate all possible 2^n subsequences of the input array. For each subsequence, we calculate the sum of its elements. These sums are then collected, sorted in descending order, and the k-th element is selected as the result. This method is exhaustive and guarantees the correct answer but is computationally expensive.

Algorithm

Create a list, sums, to store the subsequence sums.
Iterate from i = 0 to 2^n - 1. Each i represents a bitmask for a subsequence.
For each i, initialize currentSum = 0.
Iterate from j = 0 to n - 1.
If the j-th bit is set in i, add nums[j] to currentSum.
After the inner loop, add currentSum to the sums list.
Sort the sums list in descending order.
Return the element at index k - 1 in the sorted list.

The core of this method is the generation of all subsequences. This can be achieved using recursion (backtracking) or iteratively using bit manipulation. In the bit manipulation approach, each integer from 0 to 2^n - 1 represents a unique subsequence. The j-th bit of an integer i corresponds to the j-th element of nums. If the j-th bit is set, the j-th element is included in the subsequence corresponding to i. After computing all 2^n sums, a standard sorting algorithm is used to order them, from which the k-th largest is easily retrieved.

public long kSum(int[] nums, int k) {
    int n = nums.length;
    List<Long> sums = new ArrayList<>();
    // Iterate through all possible subsequences using bitmask
    for (int i = 0; i < (1 << n); i++) {
        long currentSum = 0;
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) != 0) {
                currentSum += nums[j];
            }
        }
        sums.add(currentSum);
    }
    Collections.sort(sums, Collections.reverseOrder());
    return sums.get(k - 1);
}

Complexity Analysis

Time Complexity: `O(n * 2^n)` for generating and summing all subsequences, plus `O(2^n * log(2^n))` for sorting. The total is `O(n * 2^n)`.Space Complexity: `O(2^n)` to store all the subsequence sums.

Pros and Cons

Pros:

Conceptually simple and easy to implement.
Guaranteed to be correct.

Cons:

Extremely high time and space complexity.
Infeasible for the given constraints where n can be up to 10^5.

Code Solutions

Checking out 3 solutions in different languages for Find the K-Sum of an Array. Click on different languages to view the code.

class Solution { public long kSum ( int [] nums , int k ) { long mx = 0 ; int n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { if ( nums [ i ] > 0 ) { mx += nums [ i ]; } else { nums [ i ] *= - 1 ; } } Arrays . sort ( nums ); PriorityQueue < Pair < Long , Integer >> pq = new PriorityQueue <>( Comparator . comparing ( Pair: : getKey )); pq . offer ( new Pair <>( 0L , 0 )); while (-- k > 0 ) { var p = pq . poll (); long s = p . getKey (); int i = p . getValue (); if ( i < n ) { pq . offer ( new Pair <>( s + nums [ i ], i + 1 )); if ( i > 0 ) { pq . offer ( new Pair <>( s + nums [ i ] - nums [ i - 1 ], i + 1 )); } } } return mx - pq . peek (). getKey (); } }

Video Solution

Watch the video walkthrough for Find the K-Sum of an Array

Algorithms:

Sorting

Data Structures:

ArrayHeap (Priority Queue)

Companies:

Hubspot |