K-th Largest Sum Contiguous Subarray

JavaView on GFG

Problem Overview

Find kth largest sum among all contiguous subarrays.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find kth largest sum among all contiguous subarrays. Min-heap of size k.

Algorithm

1Compute all prefix sums. For each pair (i,j): subarray sum = prefix[j]-prefix[i-1]. Use min-heap of size k.

Common Pitfalls

• O(n^2 log k) with heap. For large arrays: more advanced approaches needed. All O(n^2) subarray sums considered.

K-th Largest Sum Contiguous Subarray.java

Java

// Approach: Compute all subarray sums (prefix sums), then find kth largest using min-heap of size k.
// Time: O(n^2 log k) Space: O(n^2)
import java.util.*;

class Solution {
    public static int kthLargest(int[] arr, int k) {
        int n = arr.length;

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        int last = 0;
        for (int i = 0; i < n; i++) {
            last += arr[i];
            pq.add(last);

            if (pq.size() > k)
                pq.poll();
            int sum = last;
            for (int j = 0; j < i; j++) {
                sum -= arr[j];

                pq.add(sum);

                if (pq.size() > k)
                    pq.poll();
            }

        }

        return pq.peek();
    }
}

Was this solution helpful?