Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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.length1 <= n <= 105-109 <= nums[i] <= 1091 <= k <= min(2000, 2n)Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[2,4,-2] 5
[1,-2,3,4,-10,12] 16
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2386: Find the K-Sum of an Array
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();
}
}
// Accepted solution for LeetCode #2386: Find the K-Sum of an Array
func kSum(nums []int, k int) int64 {
mx := 0
for i, x := range nums {
if x > 0 {
mx += x
} else {
nums[i] *= -1
}
}
sort.Ints(nums)
h := &hp{{0, 0}}
for k > 1 {
k--
p := heap.Pop(h).(pair)
if p.i < len(nums) {
heap.Push(h, pair{p.sum + nums[p.i], p.i + 1})
if p.i > 0 {
heap.Push(h, pair{p.sum + nums[p.i] - nums[p.i-1], p.i + 1})
}
}
}
return int64(mx) - int64((*h)[0].sum)
}
type pair struct{ sum, i int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].sum < h[j].sum }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
# Accepted solution for LeetCode #2386: Find the K-Sum of an Array
class Solution:
def kSum(self, nums: List[int], k: int) -> int:
mx = 0
for i, x in enumerate(nums):
if x > 0:
mx += x
else:
nums[i] = -x
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]
// Accepted solution for LeetCode #2386: Find the K-Sum of an Array
/**
* [2386] Find the K-Sum of an Array
*/
pub struct Solution {}
// submission codes start here
use std::collections::BinaryHeap;
#[derive(PartialEq, Eq)]
struct Node {
sum: i64,
last: usize,
}
impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
other.sum.partial_cmp(&self.sum)
}
}
impl Ord for Node {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.sum.cmp(&self.sum)
}
}
impl Solution {
pub fn k_sum(nums: Vec<i32>, k: i32) -> i64 {
let mut total = 0;
let mut nums: Vec<i64> = nums
.iter()
.map(|x| {
if *x > 0 {
let x = *x as i64;
total += x;
x
} else {
-x as i64
}
})
.collect();
nums.sort_unstable();
let mut heap = BinaryHeap::new();
heap.push(Node {
sum: nums[0],
last: 0,
});
let mut result = 0;
for _ in 1..k {
let top = heap.pop().unwrap();
result = top.sum;
if top.last == nums.len() - 1 {
continue;
}
heap.push(Node {
sum: top.sum + nums[top.last + 1],
last: top.last + 1,
});
heap.push(Node {
sum: top.sum - nums[top.last] + nums[top.last + 1],
last: top.last + 1,
});
}
total - result
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_2386() {
assert_eq!(2, Solution::k_sum(vec![2, 4, -2], 5));
}
}
// Accepted solution for LeetCode #2386: Find the K-Sum of an Array
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #2386: Find the K-Sum of an Array
// 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();
// }
// }
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.