Find the K-Sum of an Array

Hard

#2172Time: `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: `O(2^n)` to store all the subsequence sums.1 company

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)

Companies

Hubspot

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1public long kSum(int[] nums, int k) {2    int n = nums.length;3    List<Long> sums = new ArrayList<>();4    // Iterate through all possible subsequences using bitmask5    for (int i = 0; i < (1 << n); i++) {6        long currentSum = 0;7        for (int j = 0; j < n; j++) {8            if ((i & (1 << j)) != 0) {9                currentSum += nums[j];10            }11        }12        sums.add(currentSum);13    }14    Collections.sort(sums, Collections.reverseOrder());15    return sums.get(k - 1);16}

Complexity

Time

`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

`O(2^n)` to store all the subsequence sums.

Trade-offs

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.

A highly efficient approach hinges on a clever transformation of the problem. Instead of dealing with positive and negative numbers, we can reframe the problem as finding the k-th smallest "deviation" from a maximum possible sum. This simplifies the search space and allows us to use a min-heap to efficiently find the desired value, leveraging the small constraint on k.

Algorithm

Initialize maxSum = 0. Iterate through nums, adding all positive numbers to maxSum.
Convert every number in nums to its absolute value.
Sort the modified nums array (which now contains absolute values) in ascending order.
If k is 1, the answer is maxSum (corresponding to a deviation of 0).
Initialize a min-priority queue pq to store pairs of {deviation_sum, index}.
Push the smallest non-zero deviation, {nums[0], 0}, into pq.
Initialize currentDeviation = 0.
Loop k-1 times (from i=1 to k-1):
- Pop the top element {sum, idx} from pq. This is the next smallest deviation. Set currentDeviation = sum.
- If idx + 1 is within the array bounds:
  - Generate a new candidate by adding the next element: sum + nums[idx + 1]. Push {sum + nums[idx + 1], idx + 1} to pq.
  - Generate another candidate by replacing the current element with the next: (sum - nums[idx]) + nums[idx + 1]. Push {(sum - nums[idx]) + nums[idx + 1], idx + 1} to pq.
The final answer is maxSum - currentDeviation.

Walkthrough

First, we observe that the largest possible subsequence sum is achieved by taking all positive numbers. Let's call this maxSum. Any other subsequence sum S can be seen as maxSum minus some value. This "deviation" comes from two sources: not including a positive number p (which is like subtracting p from maxSum) or including a negative number n (which is like subtracting abs(n) from maxSum). Therefore, any subsequence sum S can be written as S = maxSum - deviation, where deviation is a sum of a subsequence of abs(nums). Finding the k-th largest S is equivalent to finding the k-th smallest deviation. The problem is now reduced to: find the k-th smallest subsequence sum of an array of non-negative numbers (abs(nums)). We can solve this efficiently using a min-heap. We sort abs(nums) and use the heap to generate the smallest subsequence sums in order. The smallest deviation is 0 (from an empty subsequence). We initialize the heap with the next smallest deviation (abs(nums)[0]) and iteratively generate larger deviations by either adding the next element or replacing the last added element. We repeat this k-1 times to find the k-th smallest deviation.

1import java.util.*;2 3class Solution {4    public long kSum(int[] nums, int k) {5        int n = nums.length;6        long maxSum = 0;7        for (int i = 0; i < n; i++) {8            if (nums[i] > 0) {9                maxSum += nums[i];10            }11            nums[i] = Math.abs(nums[i]);12        }13 14        Arrays.sort(nums); // nums now contains absolute values, sorted15 16        // Min-heap to store {deviation_sum, index}17        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));18        19        long currentDeviation = 0;20        if (n > 0) {21            pq.offer(new long[]{nums[0], 0});22        }23 24        // We already have the 1st largest sum (maxSum), which corresponds to deviation 0.25        // We find the k-th smallest deviation by popping from the heap k-1 times.26        for (int i = 1; i < k; i++) {27            long[] top = pq.poll();28            currentDeviation = top[0];29            int index = (int) top[1];30 31            if (index + 1 < n) {32                // Option 1: Add the next element to the current subsequence33                pq.offer(new long[]{currentDeviation + nums[index + 1], index + 1});34                35                // Option 2: Replace the last element of the current subsequence with the next one36                pq.offer(new long[]{currentDeviation - nums[index] + nums[index + 1], index + 1});37            }38        }39 40        return maxSum - currentDeviation;41    }42}

Complexity

Time

`O(n log n + k log k)`. Sorting the absolute values takes `O(n log n)`. The heap operations involve `k-1` extractions and about `2*(k-1)` insertions, with heap size up to `O(k)`, leading to `O(k log k)`. Total time is `O(n log n)`.

Space

`O(n)`. `O(n)` to store the absolute values (if not done in-place) and `O(k)` for the priority queue.

Trade-offs

Pros

Highly efficient, with time complexity dominated by sorting.
Effectively utilizes the small k constraint.
Reduces a complex problem to a standard heap-based search.

Cons

The core insight of problem transformation is not immediately obvious.
The logic for generating new candidates for the heap requires careful reasoning.

Solutions

Solution

1class 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 (); } }

1using pli = pair < long long , int > ; class Solution { public: long long kSum ( vector < int >& nums , int k ) { long long mx = 0 ; int n = nums . size (); for ( int i = 0 ; i < n ; ++ i ) { if ( nums [ i ] > 0 ) { mx += nums [ i ]; } else { nums [ i ] *= - 1 ; } } sort ( nums . begin (), nums . end ()); priority_queue < pli , vector < pli > , greater < pli >> pq ; pq . push ({ 0 , 0 }); while ( -- k ) { auto p = pq . top (); pq . pop (); long long s = p . first ; int i = p . second ; if ( i < n ) { pq . push ({ s + nums [ i ], i + 1 }); if ( i ) { pq . push ({ s + nums [ i ] - nums [ i - 1 ], i + 1 }); } } } return mx - pq . top (). first ; } };

1class Solution : def kSum ( self , nums : List [ int ], k : int ) -> int : mx = 0 for i , v in enumerate ( nums ): if v > 0 : mx += v else : nums [ i ] = - v nums . sort () h = [( 0 , 0 )] for _ in range ( k - 1 ): s , i = heappop ( h ) if i < len ( nums ): heappush ( h , ( s + nums [ i ], i + 1 )) if i : heappush ( h , ( s + nums [ i ] - nums [ i - 1 ], i + 1 )) return mx - h [ 0 ][ 0 ]

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 problem