2386. Find the K-Sum of an Array LeetCode Solution

Last updated: February 27, 2025

In this guide, you will get 2386. Find the K-Sum of an Array LeetCode Solution with the best time and space complexity. The solution to Find the K-Sum of an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find the K-Sum of an Array solution in C++
Find the K-Sum of an Array solution in Java
Find the K-Sum of an Array solution in Python
Additional Resources

2386. Find the K-Sum of an Array LeetCode Solution image

Problem Statement of Find the K-Sum of an Array

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)

Complexity Analysis

Time Complexity: O(\max(\texttt{sort}(\texttt{nums}), k\log k))
Space Complexity: O(n + k)

2386. Find the K-Sum of an Array LeetCode Solution in C++

class Solution {
 public:
  long long kSum(vector<int>& nums, int k) {
    const long long maxSum = getMaxSum(nums);
    const vector<int> absNums = getAbsNums(nums);
    long long ans = maxSum;
    // (the next maximum sum, the next index i)
    using P = pair<long long, int>;
    priority_queue<P> maxHeap;
    maxHeap.emplace(maxSum - absNums[0], 0);

    for (int j = 0; j < k - 1; ++j) {
      const auto [nextMaxSum, i] = maxHeap.top();
      maxHeap.pop();
      ans = nextMaxSum;
      if (i + 1 < absNums.size()) {
        maxHeap.emplace(nextMaxSum - absNums[i + 1], i + 1);
        maxHeap.emplace(nextMaxSum - absNums[i + 1] + absNums[i], i + 1);
      }
    }

    return ans;
  }

 private:
  long long getMaxSum(const vector<int>& nums) {
    long long maxSum = 0;
    for (const int num : nums)
      if (num > 0)
        maxSum += num;
    return maxSum;
  }

  vector<int> getAbsNums(const vector<int>& nums) {
    vector<int> absNums;
    for (const int num : nums)
      absNums.push_back(abs(num));
    ranges::sort(absNums);
    return absNums;
  }
};
/* code provided by PROGIEZ */

2386. Find the K-Sum of an Array LeetCode Solution in Java

class Solution {
  public long kSum(int[] nums, int k) {
    final long maxSum = getMaxSum(nums);
    final int[] absNums = getAbsNums(nums);
    long ans = maxSum;
    // (the next maximum sum, the next index i)
    Queue<Pair<Long, Integer>> maxHeap =
        new PriorityQueue<>((a, b) -> Long.compare(b.getKey(), a.getKey()));
    maxHeap.offer(new Pair<>(maxSum - absNums[0], 0));

    for (int j = 0; j < k - 1; ++j) {
      Pair<Long, Integer> pair = maxHeap.poll();
      final long nextMaxSum = pair.getKey();
      final int i = pair.getValue();
      ans = nextMaxSum;
      if (i + 1 < absNums.length) {
        maxHeap.offer(new Pair<>(nextMaxSum - absNums[i + 1], i + 1));
        maxHeap.offer(new Pair<>(nextMaxSum - absNums[i + 1] + absNums[i], i + 1));
      }
    }

    return ans;
  }

  private long getMaxSum(int[] nums) {
    long maxSum = 0;
    for (final int num : nums)
      if (num > 0)
        maxSum += num;
    return maxSum;
  }

  private int[] getAbsNums(int[] nums) {
    for (int i = 0; i < nums.length; ++i)
      nums[i] = Math.abs(nums[i]);
    Arrays.sort(nums);
    return nums;
  }
}
// code provided by PROGIEZ

2386. Find the K-Sum of an Array LeetCode Solution in Python

class Solution:
  def kSum(self, nums: list[int], k: int) -> int:
    maxSum = sum(num for num in nums if num > 0)
    absNums = sorted(abs(num) for num in nums)
    # (the next maximum sum, the next index i)
    maxHeap = [(-(maxSum - absNums[0]), 0)]
    nextMaxSum = maxSum

    for _ in range(k - 1):
      nextMaxSum, i = heapq.heappop(maxHeap)
      nextMaxSum *= -1
      if i + 1 < len(absNums):
        heapq.heappush(maxHeap, (-(nextMaxSum - absNums[i + 1]), i + 1))
        heapq.heappush(
            maxHeap, (-(nextMaxSum - absNums[i + 1] + absNums[i]), i + 1))

    return nextMaxSum
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents