PPractick

The problem

A travel site pairs one flight (price list A) with one hotel (price list B) and wants to show the K highest-value combinations A[i] + B[j] across all n² pairs, in non-increasing order. Computing all n² sums is too slow for n = 10⁵. After sorting both arrays in descending order, the best sum is A[0] + B[0], and the next best is always a neighbour of a pair already taken: (i+1, j) or (i, j+1). A max-heap exploring this grid from the top-left corner, with a visited set to avoid duplicates, yields the K best in O(K log K).

Example: A = [1, 4, 2, 3], B = [2, 5, 1, 6], K = 4 → [10, 9, 9, 8].

Function signature

vector<int> maxCombinations(vector<int> A, vector<int> B, int K);  // K <= n * n

Test cases

Input (A, B, K)	Output	Explanation
([3, 2], [1, 4], 2)	[7, 6]	3+4, 2+4
([1, 4, 2, 3], [2, 5, 1, 6], 4)	[10, 9, 9, 8]	4+6, 4+5, 3+6, 3+5
([1], [1], 1)	[2]
([5, 5], [1, 1], 4)	[6, 6, 6, 6]	Equal sums from different pairs all count
([0, -1], [-2, 3], 3)	[3, 2, -2]

(Confirm: pairs (i, j) are distinct by index, so equal sums are listed separately; output in non-increasing order.)

How interviewers phrase it

• "Given two arrays A and B of size N and an integer K, return the K maximum sum combinations from all possible pairs" (GeeksforGeeks "Maximum Sum Combination"; LeetCode 373 "Find K Pairs with Smallest Sums" is the mirror image).

Clarifying questions to ask

1. Are pairs distinguished by index? (Yes, so repeated sums appear repeatedly.)
2. What order should the output be in? (Non-increasing.)
3. How large are N and K? (N up to 10⁵, K up to N, so the n² pairs can't be enumerated.)

Follow-ups to expect

1. "Why only explore neighbours?"
2. "Why the visited set?"
3. "Alternative without a set?"
4. "Complexity?"
5. "How is this related to other problems?"

Related questions

• Replace Elements by Their Rank Easy
• Aggressive Cows Hard
• Minimize Max Distance to Gas Station Hard
• Merge K sorted Lists Hard
• Kth largest element in a stream of running integers Hard
• Find Median from Data Stream Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in