AlgoViz
HomeHeap / Priority Queue

Maximum Sum Combination

Hard

Sort both, expand from the biggest pair

Problem

Given two arrays and K, return the K largest sums formed by taking one element from each array.

In simple words

Sort both, start from the biggest pair, and use a heap to explore the next-biggest neighbours.

The idea

Sort both arrays and start from the pair of largest elements, then use a max-heap to expand to the neighbouring index pairs. A visited set stops the same pair being pushed twice, so only K pops are needed rather than all n² sums.

The trick

  • Push (i+1, j) and (i, j+1) after popping (i, j).
  • A visited set is essential — the two expansions overlap.
  • O(K log K) after the sorts, versus O(n²) for all sums.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
4
2
3
0
1
2
3

Step 1 of 2. Here's the example — A=[1,4,2,3], B=[2,5,1,6], K=4 Values: 1, 4, 2, 3.

1/2
Optimal
timeO(K log K)spaceO(K)
1sort A,B; max-heap of (A[i]+B[j]) starting at top pair2pop K times, pushing neighbours (i-1,j) and (i,j-1)

Input

array
[1, 4, 2, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
a = [3, 2], b = [1, 4], k = 2
Output:
[7, 6]
Explanation:
Top 2 pair sums: 3+4 and 2+4.

Example 2

Input:
a = [1, 4, 2, 3], b = [2, 5, 1, 6], k = 3
Output:
[10, 9, 9]
Explanation:
The three biggest cross-sums.

Example 3

Input:
a = [1], b = [1], k = 1
Output:
[2]
Explanation:
Only one pair → 2.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.