Find K-th Largest Sum Contiguous Subarray
A hard Heap problem included in Love Babbar 450. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Heap
- Sheets
- 1
- Core for
- 9 roles
- Platform
- GeeksforGeeks
The problem
Given an integer array, find the kth largest sum among all possible contiguous subarrays. A contiguous subarray is a non-empty sequence of consecutive elements. The kth largest sum is determined by sorting all subarray sums in descending order.
Example 1
- Input
- arr = [3, -1, 2], k = 3
- Output
- 2
- Why
- All contiguous subarrays and their sums: [3]=3, [3,-1]=2, [3,-1,2]=4, [-1]=-1, [-1,2]=1, [2]=2. Sorted descending: [4,3,2,2,1,-1]. The 3rd largest sum is 2.
Example 2
- Input
- arr = [2, 1, 3], k = 4
- Output
- 3
- Why
- Subarray sums: [2]=2, [2,1]=3, [2,1,3]=6, [1]=1, [1,3]=4, [3]=3. Sorted descending: [6,4,3,3,2,1]. The 4th largest is 3.
Constraints
- 1 <= arr.length <= 1000
- -10^5 <= arr[i] <= 10^5
- 1 <= k <= arr.length * (arr.length + 1) / 2
How to think about it
Updated 2026-09-09An array of length 1000 generates about 500,000 subarray sums. Storing and sorting all half a million sums is feasible but wastes memory. A bounded min-heap of size k lets you stream subarray sums as they are generated, evicting any sum that cannot beat the current kth largest.
Approaches, worst first
Generate all sums and sort
time O(n^2 log(n^2)) · space O(n^2)
Compute prefix sums, evaluate all n * (n + 1) / 2 contiguous subarray sums into a flat list, sort the list in descending order, and read index k - 1.
Running bounded min-heapWrite this one
time O(n^2 log k) · space O(k)
Iterate through every subarray start and end to compute each sum. Push into a min-heap of capacity k, popping the root when the heap exceeds k. After inspecting all pairs, the root is the kth largest sum.
Where people lose marks · 3
- Re-summing elements from scratch in O(n) for each subarray pair, driving total generation time to O(n^3). Accumulate the sum incrementally as the inner loop extends the subarray.
- Memory limit exhaustion when allocating an array of size O(n^2) in constrained environments. The bounded heap keeps peak memory strictly proportional to k.
- Subarray sums can be negative because arr[i] can be negative. Never initialize candidate sums or heap guards to 0.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
What each operation costs
| Operation | Time |
|---|---|
| read the minimum or maximum element | O(1) |
| insert a new element and sift into position | O(log n) |
| remove the top element and sift down | O(log n) |
| build a heap from an array of n items | O(n) |
What usually goes wrong with Heap
- Using a max-heap instead of a min-heap when keeping the k largest elements, causing the largest values to be evicted while small items stay behind.
- Assuming that extracting elements by iterating over the backing array yields sorted order, without popping items from the heap one by one.
- Forgetting that standard language libraries provide a min-heap by default, leading to wrong answers when a max-heap was required.
Which roles need this problem
Heap is a core topic for these 9 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 11 more roles, including SDE / Backend Engineer, Data Engineer, ML Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Heap problems
Problem set and role mapping as of .