Find the k sum of an array

Array Sorting Heap (Priority Queue)

41.2% acceptance

Feb 25, 2026

608

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;


impl Solution {
  pub fn k_sum(nums: Vec<i32>, k: i32) -> i64 {
    let max_sum: i64 = nums.iter().filter(|&&x| x > 0).map(|&x| x as i64).sum();
    let mut vals: Vec<i64> = nums.iter().map(|&x| x.unsigned_abs() as i64).collect();
    vals.sort_unstable();
    let mut heap: BinaryHeap<Reverse<(i64, usize)>> = BinaryHeap::new();
    if !vals.is_empty() {
      heap.push(Reverse((vals[0], 0)));
    }
    let mut ans = max_sum;
    let mut remaining = k - 1;
    while remaining > 0 {
      if let Some(Reverse((d, i))) = heap.pop() {
        ans = max_sum - d;
        remaining -= 1;
        if i + 1 < vals.len() {
          heap.push(Reverse((d + vals[i + 1], i + 1)));
          heap.push(Reverse((d - vals[i] + vals[i + 1], i + 1)));
        }
      } else {
        break;
      }
    }
    ans
  }
}