Pattern visualizer

Find K-th Largest Sum Contiguous Subarray

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. 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..

A size-k min-heap over every subarray sum

time O(n^2 log k)space O(k)step 1 / 8

line 7

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

Where to practice Heap

Practice Heap problems All Heap problems Back to roadmap