Add solution #2386

JoshCrozier · JoshCrozier · commit 4205115126ff · 2025-08-07T23:51:12.000-05:00
diff --git a/README.md b/README.md
@@ -2164,6 +2164,7 @@
 2383|[Minimum Hours of Training to Win a Competition](./solutions/2383-minimum-hours-of-training-to-win-a-competition.js)|Easy|
 2384|[Largest Palindromic Number](./solutions/2384-largest-palindromic-number.js)|Medium|
 2385|[Amount of Time for Binary Tree to Be Infected](./solutions/2385-amount-of-time-for-binary-tree-to-be-infected.js)|Medium|
+2386|[Find the K-Sum of an Array](./solutions/2386-find-the-k-sum-of-an-array.js)|Hard|
 2387|[Median of a Row Wise Sorted Matrix](./solutions/2387-median-of-a-row-wise-sorted-matrix.js)|Medium|
 2389|[Longest Subsequence With Limited Sum](./solutions/2389-longest-subsequence-with-limited-sum.js)|Easy|
 2390|[Removing Stars From a String](./solutions/2390-removing-stars-from-a-string.js)|Medium|
diff --git a/solutions/2386-find-the-k-sum-of-an-array.js b/solutions/2386-find-the-k-sum-of-an-array.js
@@ -0,0 +1,42 @@
+/**
+ * 2386. Find the K-Sum of an Array
+ * https://leetcode.com/problems/find-the-k-sum-of-an-array/
+ * Difficulty: Hard
+ *
+ * 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.
+ */
+
+/**
+ * @param {number[]} nums
+ * @param {number} k
+ * @return {number}
+ */
+var kSum = function(nums, k) {
+  const maxSum = nums.reduce((sum, num) => sum + Math.max(0, num), 0);
+  const absoluteNums = nums.map(num => Math.abs(num)).sort((a, b) => a - b);
+  const maxHeap = new PriorityQueue((a, b) => a[0] - b[0]);
+  maxHeap.enqueue([-maxSum + absoluteNums[0], 0]);
+  let nextSum = -maxSum;
+
+  for (let iteration = 0; iteration < k - 1; iteration++) {
+    [nextSum, i] = maxHeap.dequeue();
+
+    if (i + 1 < absoluteNums.length) {
+      maxHeap.enqueue([nextSum - absoluteNums[i] + absoluteNums[i + 1], i + 1]);
+      maxHeap.enqueue([nextSum + absoluteNums[i + 1], i + 1]);
+    }
+  }
+
+  return -nextSum;
+};
