Skip to main content
Talentd

Find the K-Sum of an Array - Solution & Explanation

HardArraySortingHeap (Priority Queue)12 min readAsked at: Amazon, HubSpot, Google
Practice this problem

Problem Statement

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 kth 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 <= 105
  • -109 <= nums[i] <= 109
  • 1 <= k <= min(2000, 2n)

Approach Overview

Problem Overview: You are given an integer array and a value k. A subsequence can include any subset of elements. Each subsequence produces a sum, and the task is to return the k-th largest subsequence sum. Because the number of subsequences is 2^n, generating all sums directly is infeasible for large n. Efficient solutions rely on ordering sums and exploring them incrementally.

Approach 1: Sorting and Binary Search (Time: O(n log n + n log S), Space: O(1) or O(n))

This approach begins by transforming the problem. Compute the maximum possible subsequence sum by adding all positive numbers. Then convert all elements to their absolute values and sort them. Instead of directly finding the k-th largest sum, you search for the k-th smallest reduction from the maximum sum. Binary search runs over the possible reduction values, while a DFS-style counting routine checks how many subsequences produce a reduction ≤ the candidate. The key insight: every subsequence sum equals maxSum - reduction. Binary search efficiently narrows the k-th reduction without enumerating all subsets. This approach is useful when you want deterministic exploration with predictable complexity.

Approach 2: Max-Heap and Iterative Summation (Time: O(n log n + k log n), Space: O(n))

This is the most common interview solution. First compute the maximum subsequence sum using all positive values. Convert numbers to absolute values and sort them. Instead of generating every subsequence sum, maintain candidates using a heap (priority queue). The heap tracks the next smallest reductions from the maximum sum. Start with the smallest reduction and iteratively expand possibilities by including the next absolute value or swapping elements in the reduction set. Each heap pop reveals the next largest subsequence sum. Because you only generate up to k candidates, the algorithm avoids exponential enumeration while maintaining correct order.

Recommended for interviews: The heap-based approach is usually what interviewers expect. It demonstrates control over priority queues, incremental state expansion, and ordering of candidate sums. The binary search method also works and shows strong reasoning about monotonic search spaces. Mentioning the naive 2^n subsequence enumeration first shows understanding of the brute-force baseline, but implementing the heap approach proves you can optimize it to O(n log n + k log n).

Approach 1: Approach 1: Sorting and Binary Search

This approach involves generating all possible subsequence sums, sorting them, and then performing a binary search to find the k-th largest sum.

Given the constraints, this approach may not be feasible for the upper limits of n due to its time complexity. However, it illustrates a straightforward way to conceptualize the problem.

This solution generates all possible subsequences by using combinations from itertools, calculates their sums, and stores these in a list. The list is then sorted in descending order, and the k-th largest sum is returned by accessing the list at the k-1 index.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(2^n * n) for generating subsequences and computing sums, and O(2^n log(2^n)) for sorting.
Space Complexity: O(2^n) for storing the sums.

Try this approach in the editor →

Approach 2: Approach 2: Max-Heap and Iterative Summation

This approach uses a max-heap (priority queue) to efficiently find the k-th largest subsequence sum. This method is more effective and feasible when handling large arrays.

The idea is to add sums to the heap and always maintain only the k largest sums, popping from the heap when necessary to ensure it does not grow beyond size k.

This Python solution maintains a max-heap of sums. We start with a heap initialized with 0, signifying the empty subsequence sum. For each number, we calculate potential new sums by adding the number to each current sum in the heap, expanding the list of sums. We then keep only the largest k elements in the heap. This ensures we eventually have the k-th largest sum at the k-1 index.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n * k log k) due to maintaining a heap of size k across n iterations.
Space Complexity: O(k) for the heap storage.

Try this approach in the editor →

Approach 3: Priority Queue (Min-Heap)

First, we find the maximum subarray sum mx, which is the sum of all positive numbers.

It can be observed that the sum of other subarrays can be considered as the maximum subarray sum minus the sum of other parts of the subarray. Therefore, we can convert the problem into finding the k-th smallest subarray sum.

We only need to sort all numbers in ascending order by their absolute values, then build a min-heap to store the tuple (s, i), where s is the current sum and i is the index of the next number to be selected in the subarray.

Each time, we extract the top of the heap and insert two new situations: one is to select the next number, and the other is to select the next number but not the current number.

Since the array is sorted in ascending order, this method can traverse all subarray sums in order without omission.

The time complexity is O(n times log n + k times log k), where n is the length of the array nums. The space complexity is O(n).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Binary Search

Time Complexity: O(2^n * n) for generating subsequences and computing sums, and O(2^n log(2^n)) for sorting.
Space Complexity: O(2^n) for storing the sums.

Approach 2: Max-Heap and Iterative Summation

Time Complexity: O(n * k log k) due to maintaining a heap of size k across n iterations.
Space Complexity: O(k) for the heap storage.

Priority Queue (Min-Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Binary SearchO(n log n + n log S)O(1) - O(n)When you can exploit monotonic search on reduction values and want deterministic search without maintaining many heap states
Max-Heap and Iterative SummationO(n log n + k log n)O(n)Best general solution for interviews; efficiently generates the next largest subsequence sums using a priority queue

Video Solution

Weekly Contest 307 | 2386. Find the K-Sum of an Array • codingMohan • 5,543 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Find the K-Sum of an Array easy or hard?
Find the K-Sum of an Array is classified as Hard because the naive solution involves 2^n subsequences. Efficient solutions require recognizing that subsequence sums can be expressed as reductions from the maximum sum and explored using heaps or binary search techniques.
Find the K-Sum of an Array Python/Java solution
Python implementations typically use the heapq module to maintain the priority queue. Java solutions use PriorityQueue with custom pair states storing the current reduction and index. Both implementations follow the same logic: compute the maximum sum, sort absolute values, and iteratively generate k candidates.
What is the best approach for Find the K-Sum of an Array?
The most practical approach uses a max sum baseline and a min-heap (priority queue) to generate the next smallest reductions. After sorting the absolute values, the heap tracks candidate reductions and expands them iteratively. This method runs in O(n log n + k log n) time and avoids enumerating all 2^n subsequences.
Is Find the K-Sum of an Array asked at Google/Amazon/Meta?
Problems involving k-th largest combinations, heap exploration, and subsequence sums are common at companies like Google, Amazon, and Meta. Variants frequently test priority queues, combinatorial enumeration, and pruning techniques. This problem specifically evaluates your ability to avoid exponential enumeration.
What data structure is used in Find the K-Sum of an Array?
The key data structure is a heap (priority queue). It maintains candidate subsequence reductions in sorted order so the algorithm can extract the next best sum efficiently. Sorting and array traversal are also used to structure the candidate generation process.
What is the time complexity of Find the K-Sum of an Array?
The optimal heap-based solution runs in O(n log n + k log n) time. Sorting the array costs O(n log n), and each of the k heap operations costs O(log n). Space complexity is O(n) due to the priority queue and auxiliary structures.
How to solve Find the K-Sum of an Array in O(n log n + k log n)?
First compute the maximum subsequence sum by adding all positive numbers. Convert values to absolute numbers and sort them. Use a min-heap to track the smallest reductions from the maximum sum. Repeatedly pop the smallest reduction and push new candidate states until the k-th subsequence sum is produced.

Ready to solve this problem?

Practice Find the K-Sum of an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays