Kth largest sum of contiguous subarrays

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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];
}