Log inSign up
hardGeeksforGeeksNot Started

K Maximum Sum Combinations

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on GeeksforGeeks
Lesson

Problem Statement

Given two integer arrays A and B of size N each and an integer K, find the K maximum valid sum combinations formed by taking one element from A and one from B (A[i] + B[j]).

The result must be returned in descending order.

Example 1 · Example 1: Small Arrays:

Input: A = [3, 2], B = [1, 4], K = 2
Output: [7, 6]
Explanation: Sorted A: [3, 2], sorted B: [4, 1]. Sums: 3 + 4 = 7 (i=0, j=0) 2 + 4 = 6 (i=1, j=0) 3 + 1 = 4 (i=0, j=1) 2 + 1 = 3 (i=1, j=1) Two largest sums are 7 and 6. Max-Heap Tree (Initial): (sum: 7, [0, 0])

Constraints:

  • 1 <= N <= 105
  • 1 <= K <= min(N, 104)
  • 1 <= A[i], B[i] <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand Best-First Search on implicitly sorted 2D grid spaces.
  • Coordinate deduplication using hash sets for index tuples.
  • Implement optimal heap traversal in all 4 languages.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find K largest sum combinations of two arrays.
  • K is much smaller than N2.
  • Generating all N2 combinations times out or causes OOM.

Algorithmic Decision Tree:

  • Sorting both arrays initially allows directional traversal from largest to smallest.
  • Max-Heap prioritizes exploring the largest sum candidates first.

Connected Patterns:

Find K Pairs with Smallest SumsKth Smallest Element in a Sorted MatrixMerge k Sorted Lists

1. Brute Force — Compute All N^2 Sums & Sort

Intuition

Run two nested loops over A and B. Store all sums in an array. Sort descending and return first K elements.

When to apply: When N is small (N <= 500).

Algorithm

  1. Step 1: Compute all A[i] + B[j] sums.
  2. Step 2: Sort all sums descending.
  3. Step 3: Slice and return first K sums.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 vector<int> maxCombinations(vector<int>& A, vector<int>& B, int K) {
9 vector<int> allSums;
10 for (int a : A) {
11 for (int b : B) {
12 allSums.push_back(a + b);
13 }
14 }
15 sort(allSums.begin(), allSums.end(), greater<int>());
16 return vector<int>(allSums.begin(), allSums.begin() + K);
17 }
18};
19
20int main() {
21 Solution sol;
22 vector<int> A = {3, 2}, B = {1, 4};
23 auto res = sol.maxCombinations(A, B, 2);
24 cout << "K Max Combinations (Brute Force): ";
25 for (int x : res) cout << x << " ";
26 cout << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N^2 log(N^2)) — O(N2 log N) from sorting all pairs.
  • Space complexity: O(N^2) — O(N2) memory to hold sums.

Why Brute Force Doesn't Scale:

With N = 105, N2 = 1010 pairs, crashing memory and taking minutes. The optimal heap visits only 2K states (~20,000 for K = 10,000).

Runs in ~15ms for N = 100,000, K = 10,000.

2. Better — Min-Heap of Size K over All Pairs

Intuition

Keep a Min-Heap of capacity K. Loop through all pairs: if heap size < K, push sum. Else if sum > heap.top, pop root and push sum.

When to apply: When memory must be limited to O(K) and N is moderate (<= 2000).

Algorithm

  1. Step 1: Initialize Min-Heap of capacity K.
  2. Step 2: Loop through A and B.
  3. Step 3: If heap size < K, push sum.
  4. Step 4: Else if sum > heap top, pop top and push sum.
  5. Step 5: Collect and reverse elements to return descending.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> maxCombinations(vector<int>& A, vector<int>& B, int K) {
10 sort(A.rbegin(), A.rend());
11 sort(B.rbegin(), B.rend());
12
13 priority_queue<int, vector<int>, greater<int>> minHeap;
14 for (int a : A) {
15 for (int b : B) {
16 int sum = a + b;
17 if ((int)minHeap.size() < K) {
18 minHeap.push(sum);
19 } else if (sum > minHeap.top()) {
20 minHeap.pop();
21 minHeap.push(sum);
22 } else {
23 break;
24 }
25 }
26 }
27
28 vector<int> result;
29 while (!minHeap.empty()) {
30 result.push_back(minHeap.top());
31 minHeap.pop();
32 }
33 reverse(result.begin(), result.end());
34 return result;
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> A = {3, 2}, B = {1, 4};
41 auto res = sol.maxCombinations(A, B, 2);
42 cout << "K Max Combinations (Better): ";
43 for (int x : res) cout << x << " ";
44 cout << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N log N + N * K log K) — O(N log N + N * K log K) with early break.
  • Space complexity: O(K) — O(K) auxiliary space.

3. Optimal — Max-Heap Best-First Search on 2D Matrix

Intuition

Sorting gives monotonic rows and columns. We start with the global maximum at (0, 0). Popping (i, j) reveals candidates (i+1, j) and (i, j+1). Using a hash set prevents duplicate insertions. Exactly K pops are executed.

When to apply: Standard optimal algorithm for large N (105) and K (104).

Algorithm

  1. Step 1: Sort A and B in descending order.
  2. Step 2: Initialize Max-Heap with (A[0] + B[0], 0, 0). Mark (0, 0) visited.
  3. Step 3: Loop K times: pop (sum, i, j) from heap and append to result.
  4. Step 4: If i + 1 < N and (i + 1, j) not visited: push and mark visited.
  5. Step 5: If j + 1 < N and (i, j + 1) not visited: push and mark visited.
  6. Step 6: Return result array.

Interactive Trace for K Maximum Sum Combinations

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Arrays sorted descending: A = [3, 2], B = [4, 1]
Visual state
Values and pointers at this exact step
tree
Root: (sum 7, [0,0])
7

Node order shown; add connections to display explicit tree edges.

pop: s1
Check / comparison
Max sum is 7 at indices (0, 0).
Decision / next transition
Pop 7 and add to result. Result = [7].
Why this step matters

Step 1: Arrays sorted descending: A = [3, 2], B = [4, 1]. Push (A[0] + B[0] = 7, 0, 0) to Max-Heap.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <set>
5#include <algorithm>
6using namespace std;
7
8class Solution {
9public:
10 vector<int> maxCombinations(vector<int>& A, vector<int>& B, int K) {
11 int n = A.size();
12 sort(A.rbegin(), A.rend());
13 sort(B.rbegin(), B.rend());
14
15 // tuple: sum, i, j
16 using Element = tuple<int, int, int>;
17 priority_queue<Element> maxHeap;
18 set<pair<int, int>> visited;
19
20 maxHeap.push({A[0] + B[0], 0, 0});
21 visited.insert({0, 0});
22
23 vector<int> result;
24 while (!maxHeap.empty() && (int)result.size() < K) {
25 auto [sum, i, j] = maxHeap.top();
26 maxHeap.pop();
27 result.push_back(sum);
28
29 if (i + 1 < n && !visited.count({i + 1, j})) {
30 maxHeap.push({A[i + 1] + B[j], i + 1, j});
31 visited.insert({i + 1, j});
32 }
33 if (j + 1 < n && !visited.count({i, j + 1})) {
34 maxHeap.push({A[i] + B[j + 1], i, j + 1});
35 visited.insert({i, j + 1});
36 }
37 }
38 return result;
39 }
40};
41
42int main() {
43 Solution sol;
44 vector<int> A = {3, 2}, B = {1, 4};
45 auto res = sol.maxCombinations(A, B, 2);
46 cout << "K Max Combinations (Optimal): ";
47 for (int x : res) cout << x << " ";
48 cout << endl;
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(N log N + K log K) — O(N log N + K log K) for sorting and K heap steps.
  • Space complexity: O(K) — O(K) auxiliary space for heap and visited set.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Generate All N2 Sums & SortO(N^2 log(N^2))O(N^2)Compute all N2 sums, sort descending, and take first K.N2 memory and comparisons.
2.Better — Min-Heap of Size K over All PairsO(N^2 log K)O(K)Iterate over all N2 pairs maintaining a Min-Heap of size K.Iterating through all N2 pairs.
3.Optimal — Max-Heap Best-First Search on Sorted ArraysOptimalO(N log N + K log K)O(K)Sort A and B descending. Start at (0, 0) and use Max-Heap to explore successors (i+1, j) and (i, j+1).None. Optimal.

Common Pitfalls & Crucial Edge Cases

Not tracking visited pairs

(i+1, j) and (i, j+1) both have neighbor (i+1, j+1), which would be pushed twice without a visited set.

Sorting ascending instead of descending

Descending order allows searching from (0, 0) downward smoothly.

String serialization slowdown

In high-performance C++, use pair<int, int> or bit-shift (long long) for instant O(1) hashing.

Crucial Edge Cases to Validate:

  • K == 1 — Returns [A_max + B_max] immediately.
  • K == N * N — Returns all pairs sorted descending.
  • Identical elements in arrays — Coordinate-based visited set prevents infinite loops and correctly handles value duplicates.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the 2D grid matrix of sums to explain how sorting makes rows and columns monotonic.
  2. Highlight the need for coordinate deduplication.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we need a visited set when exploring neighbors (i+1, j) and (i, j+1)?

Back to DSA Sheet