GeeksforGeeks Medium

Maximum Sum Combination

From arrays A and B, return the k largest sums A[i] + B[j] over all pairs.

heaparray

02

Intuition

Sort both descending: A[0]+B[0] is the biggest sum. Each popped pair (i,j) has exactly two 'next best' candidates, (i+1,j) and (i,j+1) — a max-heap frontier explores the n² grid of sums best-first, touching only ~k cells.

How to spot this pattern

Both arrays sorted descending means the best pair is (0, 0), and the next best is always a neighbour of something already taken. That's the k-way frontier pattern: keep a heap of candidates, pop the best, and push only the cells adjacent to it. The seen set is essential because two different pops can reach the same cell.

03

Approach

1

Best-first over a sum matrix

Imagine the (i,j) grid of sums, sorted axes make it decrease right and down. The k largest live in a staircase near the corner.

2

Heap + visited set

Pop the max, emit it, push its two neighbours if unseen. The visited set stops (i+1,j) arriving twice via different parents.

3

Why it's fast

Each emit pushes ≤ 2 nodes → heap stays O(k); total O(k log k) instead of n² sums.

04

Solution & live demo

▶1import heapq
▶2 
▶3def max_sum_combinations(a, b, k):
▶4    a.sort(reverse=True); b.sort(reverse=True)
▶5    heap = [(-(a[0] + b[0]), 0, 0)]
▶6    seen, res = {(0, 0)}, []
▶7    while len(res) < k:
▶8        s, i, j = heapq.heappop(heap)
▶9        res.append(-s)
▶10        for ni, nj in ((i + 1, j), (i, j + 1)):
▶11            if ni < len(a) and nj < len(b) and (ni, nj) not in seen:
▶12                seen.add((ni, nj))
▶13                heapq.heappush(heap, (-(a[ni] + b[nj]), ni, nj))
▶14    return res

05

Common pitfalls

Building all n×m sums

✗ Wrong

sums = sorted((x + y for x in a for y in b), reverse=True)
return sums[:k]

✓ Right

heap = [(-(a[0] + b[0]), 0, 0)]
# expand only the frontier

That's O(nm log nm) work and memory for the k largest values. The heap only ever holds the frontier, so the cost is O(k log k) regardless of how large the arrays are.

Omitting the visited set

✗ Wrong

for ni, nj in ((i + 1, j), (i, j + 1)):
    heapq.heappush(heap, (-(a[ni] + b[nj]), ni, nj))

✓ Right

if (ni, nj) not in seen:
    seen.add((ni, nj))
    heapq.heappush(heap, ...)

Cell (1, 1) is reachable from both (0, 1) and (1, 0), so without the guard the same sum is pushed twice and appears twice in the output. The set makes each cell enter the heap exactly once.

Forgetting to negate for a max-heap

✗ Wrong

heap = [(a[0] + b[0], 0, 0)]

✓ Right

heap = [(-(a[0] + b[0]), 0, 0)]

heapq only pops minimums, so storing raw sums yields the k smallest combinations. Values are negated going in and negated again coming out.

06

Edge cases

k = 1

Just A[0]+B[0] after sorting — one pop.

Duplicate sums

Different (i,j) cells may tie; both count, the set dedupes cells not values.

07

Complexity

Time

O(n log n + k log k)

Space

O(k)

Sorts + best-first frontier.