Maximum Sum Combination
From arrays A and B, return the k largest sums A[i] + B[j] over all pairs.
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.
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
python
▶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
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.
06
Complexity
Time
O(n log n + k log k)
Space
O(k)
Sorts + best-first frontier.