Maximum Sum Combinations

geeksforgeeks.org

Problem Statement

Given two arrays:

A[]
B[]

Find the top K maximum values of:

A[i] + B[j]

---

Brute Force Intuition

Generate every possible pair:

A[i] + B[j]

Store all sums.

Sort.

Take top K.

Complexity

• Time Complexity: O(N² log N²)
• Space Complexity: O(N²)

Brute Force Code

for(i)
   for(j)
      sums.add(A[i] + B[j]);

Collections.sort(sums);

---

Better Approach (Your Code)

Keep only K largest sums using a Min Heap.

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

Generate all pairs.

If heap size exceeds K:

pq.poll();

---

Complexity

Metric	Complexity
Time	O(N² log K)
Space	O(K)

---

Moving Towards Optimal

Observation:

After sorting:

Largest pair

=
Largest A
+
Largest B

Suppose:

A = [1,4,2,3]

B = [2,5,1,6]

Sort:

A = [1,2,3,4]

B = [1,2,5,6]

Largest sum:

4 + 6 = 10

After taking:

(i,j)

next candidates are:

(i-1,j)

(i,j-1)

This becomes identical to:

Merge K Sorted Lists

and can be solved using:

Max Heap + Visited Set

---

Optimal Complexity

Metric	Complexity
Time	O(K log K)
Space	O(K)

---

Interview One-Liner

Sort both arrays, start from the maximum pair, and use a Max Heap with a visited set to generate only the next best K sums.

---

Pattern Learned

Top K Pair Values

=> Max Heap
=> Visited Set
=> Sorted Arrays