Kth largest sum of contiguous subarrays
Problem
Consider the sums of all contiguous subarrays. Return the kth largest of these sums.
Example 1
Input: arr = [20, -5, -1], k = 3 Output: 14
Sums: 20, 15, 14, −5, −6, −1. The 3rd largest is 14.
Also asked as: Kth largest sum continuous subarrays
Test cases
Case 1
Input: [20,-5,-1], 3 Expected: 14
Case 2
Input: [10,-10,20,-40], 6 Expected: -10
Case 3
Input: [1,2], 1 Expected: 3
Case 4
Input: [5], 1 Expected: 5
View solutionHide solution1 approach
1. All prefix sums + min-heap of size k
Time O(n² log k)Space O(k)
Every subarray sum is prefix[j] − prefix[i]. Generate them and keep the k largest in a size-k min-heap.
function kthLargestSubarraySum(a, k) { const prefix = [0]; for (const x of a) prefix.push(prefix[prefix.length - 1] + x); const heap = []; for (let i = 0; i < a.length; i++) for (let j = i + 1; j <= a.length; j++) { const s = prefix[j] - prefix[i]; let p = heap.findIndex((v) => v > s); p === -1 ? heap.push(s) : heap.splice(p, 0, s); if (heap.length > k) heap.shift(); } return heap[0];}