DSA Tracker

Visualize

K-th Largest Sum Contiguous Subarray

A size-k min-heap over every subarray sum

time O(n^2 log k)space O(k)

There are O(n^2) contiguous subarrays, so O(n^2) sums — but only the top k of them ever matter for the answer. Stream every sum through a min-heap bounded to size k: any sum too small to stay in the top k gets evicted immediately, so the heap never holds more than k values. Its root, the smallest of that top-k group, is by definition the kth largest sum overall.

Details

Animated on: Given an integer array, find the kth largest sum among all possible contiguous subarrays. Example: arr=[3,-1,2], k=3 must return 2.

Problem:K-th Largest Sum Contiguous SubarrayMedium

A size-k min-heap over every subarray sum

step 1 / 8

3

arr[0] sums to 3. Pushed onto the heap, now [3] — still under capacity k=3, so nothing is evicted yet.

Pseudocode
1FUNCTION KthLargestSum(arr, k):
2  heap <- EMPTY MIN-HEAP
3  FOR i FROM 0 TO LENGTH(arr) - 1:
4    sum <- 0
5    FOR j FROM i TO LENGTH(arr) - 1:
6      sum <- sum + arr[j]
7      PUSH sum INTO heap
8      IF SIZE(heap) > k:
9        POP-MIN(heap)
10  RETURN heap[0]

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. arr[0] sums to 3. Pushed onto the heap, now [3] — still under capacity k=3, so nothing is evicted yet.
  2. arr[0..1] sums to 2. Pushed onto the heap, now [2, 3] — still under capacity k=3, so nothing is evicted yet.
  3. arr[0..2] sums to 4. Pushed onto the heap, now [2, 3, 4] — still under capacity k=3, so nothing is evicted yet.
  4. arr[1] sums to -1. Pushing it grows the heap past capacity k=3: [-1, 2, 4, 3]. A min-heap always keeps its smallest at the top — that root is exactly the sum about to get evicted.
  5. size(heap) > k, so pop-min fires: the root (-1) is discarded. Heap shrinks back to [2, 3, 4] — always the k largest sums seen so far, smallest on top.
  6. arr[1..2] sums to 1. Push then pop-min evicts 1 from [1, 2, 4, 3] since the heap is over capacity again. Heap settles at [2, 3, 4] — same push-then-evict shape every pair follows.
  7. arr[2] sums to 2. Push then pop-min evicts 2 from [2, 2, 4, 3] since the heap is over capacity again. Heap settles at [2, 3, 4] — same push-then-evict shape every pair follows.
  8. Every contiguous subarray of arr=[3, -1, 2] has been folded through the heap. Its root, 2, is the smallest of the top 3 sums — by definition the 3rd largest sum overall, matching the problem's own worked example.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve K-th Largest Sum Contiguous Subarray in the editorAll Heap problemsBack to roadmap