Maximum Sum Combination

Intuition

Find top k maximum sums where each sum uses one element from each of two arrays. Use a max-heap with already-seen pair tracking.

Algorithm

1Sort both arrays descending.
2Max-heap starting with (A[0]+B[0], 0, 0).
3Pop max, add to result, push (i+1,j) and (i,j+1) if not seen.

Common Pitfalls

•Use a visited set to avoid duplicate pairs. K iterations yields top K sums.

Maximum Sum Combination.java

Java

// Approach: Sort both arrays descending. Max-heap initialized with (a[0]+b[0]). Expand by incrementing indices.
// Time: O(k log k) Space: O(k)
import java.util.*;

class Solution {
    public ArrayList<Integer> topKSumPairs(int[] A, int[] B, int K) {
        int N = A.length;
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(A);
        Arrays.sort(B);
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = N - 1; i > N - 1 - K; i--) {
            for (int j = N - 1; j > N - 1 - K; j--) {
                int sum = A[i] + B[j];
                if (pq.size() < K)
                    pq.add(sum);
                else if (sum > pq.peek()) {
                    pq.poll();
                    pq.add(sum);
                } else
                    break;
            }
        }

        while (pq.size() > 0)
            list.add(0, pq.poll());

        return list;
    }
}

Was this solution helpful?