273. Kth Largest Sum Among All Contiguous Subarrays

Given an array of n integers, consider the sum of every contiguous subarray (there are n(n+1)/2 of them in total, and equal sums are counted separately, once per subarray). Find the kth largest such sum.

Input: The first line contains an integer n. The second line contains n space-separated integers. The third line contains the integer k. Output: Print a single integer - the kth largest sum among all contiguous subarrays.

1 <= n <= 1000, 1 <= k <= n*(n+1)/2

Generating all subarray sums still fundamentally costs O(n²) time no matter what - the heap's contribution here is specifically about avoiding O(n²) SPACE, not about beating the inherent O(n²) time needed to even enumerate every subarray.

Among the sums of every possible contiguous subarray, find the kth largest one. Brute force: Compute all n(n+1)/2 subarray sums, store them all in a list, sort the whole list, and index into the kth position - this costs O(n² log n) for the sort alone, and O(n²) space to store every sum. Optimised: A size-k-capped min-heap only ever needs to remember the k LARGEST sums seen so far, discarding anything smaller immediately - this avoids ever storing all n(n+1)/2 sums at once, keeping space down to O(k) instead of O(n²).

Use two nested loops to compute the sum of every one of the n(n+1)/2 contiguous subarrays, store all of these sums in a list, sort the list in descending order, and read off the element at index k-1. This is straightforward and correct because it directly materializes and orders every possible subarray sum, but sorting a list of quadratic size adds an extra logarithmic factor on top of an already quadratic generation step. Time: O(n^2 log n) Space: O(n^2)

Generate the same n(n+1)/2 subarray sums with nested loops, but instead of collecting them all and sorting, maintain a min-heap that is only ever allowed to hold k elements: push each new sum, and if the heap's size exceeds k, pop the smallest. After all sums have been processed, the heap's minimum is exactly the k-th largest sum overall. This avoids the cost of a full sort and the memory of storing every sum simultaneously, since the heap only ever needs to track the k largest values seen so far. Time: O(n^2 log k) Space: O(k)

Binary search over the possible range of subarray sum values, and for each candidate value mid, count how many contiguous subarrays have a sum of at least mid using prefix sums together with an efficient counting technique (such as a merge-sort-based count or a Binary Indexed Tree over the prefix sums), which counts, for every right endpoint, how many earlier prefix sums are small enough to push the subarray sum past mid. Adjust the binary search bounds based on whether the count is at least k, converging on the exact k-th largest sum. This trades the quadratic generation of every individual sum for a logarithmic number of near-linear counting passes, which scales better as n grows. Time: O(n log n log(sumRange)) Space: O(n)

1. For each possible starting index, extend the subarray one element at a time, tracking a running sum as you go. 2. Push each running sum into a min-heap capped at size k (popping the smallest whenever the heap exceeds size k). 3. After every subarray sum has been considered, the heap's top is exactly the kth largest sum.

Time: O(n² log k) - generating all n(n+1)/2 subarray sums, each triggering an O(log k) heap operation. Space: O(k), for the capped heap (a massive improvement over storing all O(n²) sums).

k = 1 (the maximum subarray sum), k = n*(n+1)/2 (the minimum subarray sum), and negative elements producing equal subarray sums that must still be counted separately.

Be ready to point out the space savings explicitly (O(k) instead of O(n²)) as the main benefit of the heap-based approach here - the TIME complexity isn't dramatically better than sorting all sums, but the SPACE savings can be the deciding factor for large n.