Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Maximum Sum Combination

HARDProblemSolveExternal Links

Description

Given two integer arrays a[] and b[] of equal size n, and a positive integer k, find the top k maximum sum combinations.

A sum combination is formed by picking one element from array a and one element from array b and adding them together. Each index from both arrays can participate in multiple combinations (we are not pairing indices; we are pairing values).

Return the k largest sums in non-increasing (descending) order.

Examples

Example 1

Input: a = [3, 2], b = [1, 4], k = 2

Output: [7, 6]

Explanation: All possible sum combinations by pairing one element from a with one from b:

  • a[0] + b[0] = 3 + 1 = 4
  • a[0] + b[1] = 3 + 4 = 7
  • a[1] + b[0] = 2 + 1 = 3
  • a[1] + b[1] = 2 + 4 = 6

All sums: [4, 7, 3, 6]. Sorted in descending order: [7, 6, 4, 3]. The top 2 are [7, 6].

Example 2

Input: a = [1, 4, 2, 3], b = [2, 5, 1, 6], k = 3

Output: [10, 9, 9]

Explanation: With 4 elements in each array, there are 4 × 4 = 16 possible sums. The three largest are:

  • 4 + 6 = 10
  • 3 + 6 = 9
  • 4 + 5 = 9

So the answer is [10, 9, 9].

Example 3

Input: a = [1], b = [1], k = 1

Output: [2]

Explanation: Only one combination exists: 1 + 1 = 2. Since k = 1, we return [2].

Constraints

  • 1 ≤ a.size() = b.size() ≤ 10^5
  • 1 ≤ k ≤ a.size()
  • 1 ≤ a[i], b[i] ≤ 10^4

Editorial

Brute Force

Intuition

The most natural approach is to simply generate every possible sum combination. Since we pick one element from array a and one from array b, there are n × n total combinations. We can compute all of them, sort the resulting list in descending order, and pick the first k values.

Think of it like a restaurant menu with two columns: appetizers and main courses. If you want to find the k most expensive meal combinations, you could write down the price of every possible appetizer + main course pair, sort all prices from highest to lowest, and pick the top k. This is simple and correct, but if both menus have 100,000 items, you would have 10 billion combinations — far too many to handle.

Step-by-Step Explanation

Let's trace through with a = [3, 2], b = [1, 4], k = 2:

Step 1: Fix a[0] = 3. Pair it with every element in b.

  • a[0] + b[0] = 3 + 1 = 4. Store sum 4.
  • a[0] + b[1] = 3 + 4 = 7. Store sum 7.

Step 2: Fix a[1] = 2. Pair it with every element in b.

  • a[1] + b[0] = 2 + 1 = 3. Store sum 3.
  • a[1] + b[1] = 2 + 4 = 6. Store sum 6.

Step 3: All sums collected: [4, 7, 3, 6].

Step 4: Sort in descending order: [7, 6, 4, 3].

Step 5: Take the first k = 2 elements: [7, 6].

Result: [7, 6].

Brute Force — Generate All Pair Sums — Watch how we compute every possible pair sum from both arrays, collect them all, sort, and pick the top k.

Algorithm

  1. Initialize an empty list to store all pair sums.
  2. For each element a[i] in array a (i = 0 to n-1):
    a. For each element b[j] in array b (j = 0 to n-1):
    • Compute sum = a[i] + b[j].
    • Append sum to the list.
  3. Sort the list of sums in descending order.
  4. Return the first k elements of the sorted list.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> topKSumPairs(vector<int>& a, vector<int>& b, int k) {
        int n = a.size();
        vector<int> allSums;
        
        // Generate all pair sums
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                allSums.push_back(a[i] + b[j]);
            }
        }
        
        // Sort in descending order
        sort(allSums.begin(), allSums.end(), greater<int>());
        
        // Take top k
        return vector<int>(allSums.begin(), allSums.begin() + k);
    }
};
class Solution:
    def topKSumPairs(self, a: list[int], b: list[int], k: int) -> list[int]:
        n = len(a)
        all_sums = []
        
        # Generate all pair sums
        for i in range(n):
            for j in range(n):
                all_sums.append(a[i] + b[j])
        
        # Sort in descending order and take top k
        all_sums.sort(reverse=True)
        return all_sums[:k]
import java.util.*;

class Solution {
    public List<Integer> topKSumPairs(int[] a, int[] b, int k) {
        int n = a.length;
        List<Integer> allSums = new ArrayList<>();
        
        // Generate all pair sums
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                allSums.add(a[i] + b[j]);
            }
        }
        
        // Sort in descending order
        Collections.sort(allSums, Collections.reverseOrder());
        
        // Take top k
        return allSums.subList(0, k);
    }
}

Complexity Analysis

Time Complexity: O(n² log n²) = O(n² log n)

Generating all pair sums takes O(n²) time (nested loops). Sorting n² sums takes O(n² log(n²)) = O(n² · 2 log n) = O(n² log n). The sorting step dominates.

Space Complexity: O(n²)

We store all n² pair sums in a list. For n = 10^5, this would require storing 10^10 integers — approximately 40 GB of memory. This makes the approach completely impractical for large inputs.

Why This Approach Is Not Efficient

The brute force generates all n² pair sums, which is catastrophic for large n. With n = 10^5, there are 10^10 pairs — ten billion. Storing them requires ~40 GB, and sorting them takes even longer. This is both a time and memory disaster.

The core problem is that we only need k sums (where k ≤ n), but we compute all n² of them. That is like reading every book in a library to find the 3 thickest ones — massively wasteful.

Key insight: If both arrays are sorted in descending order, the largest possible sum is always a[0] + b[0]. The next largest candidates can only come from a[1] + b[0] or a[0] + b[1] — we do not need to explore all n² combinations. By exploring candidates using a max-heap and tracking which index pairs we have already visited, we can find the top k sums while examining only about k candidates, not n².

Optimal Approach - Sorting with Max-Heap and Visited Set

Intuition

Imagine both arrays are sorted from largest to smallest. The very largest sum must come from combining the largest element of a with the largest element of b — that is a[0] + b[0].

Once we take that top combination, what could be the next largest? It is either:

  • a[1] + b[0] — using the second-largest from a with the largest from b, OR
  • a[0] + b[1] — using the largest from a with the second-largest from b.

We do not know which one is bigger without comparing them, but we know the answer must be one of these two candidates. This is the key observation: at any point, the next largest sum can be found by advancing one index in either array.

This forms a natural exploration pattern starting from index pair (0, 0) and branching to (1, 0) and (0, 1), then from each of those branching further. To efficiently pick the largest candidate at each step, we use a max-heap that stores (sum, index_i, index_j) tuples. We also maintain a visited set to avoid processing the same index pair twice (since the pair (1, 1) can be reached from both (0, 1) and (1, 0)).

We repeat k times: pop the max from the heap, record the sum, and push its two neighbors (i+1, j) and (i, j+1) if they have not been visited. After k iterations, we have our answer.

Step-by-Step Explanation

Let's trace through with a = [1, 4, 2, 3], b = [2, 5, 1, 6], k = 3:

Step 1: Sort both arrays in descending order. a becomes [4, 3, 2, 1]. b becomes [6, 5, 2, 1].

Step 2: The largest possible sum is a[0] + b[0] = 4 + 6 = 10. Push (10, 0, 0) into the max-heap. Mark (0, 0) as visited.

Step 3: Pop the max from the heap: (10, 0, 0). Record sum 10 in our result. Result = [10]. Now push the two neighbors:

  • (i+1, j) = (1, 0): sum = a[1] + b[0] = 3 + 6 = 9. Push (9, 1, 0). Mark (1, 0) visited.
  • (i, j+1) = (0, 1): sum = a[0] + b[1] = 4 + 5 = 9. Push (9, 0, 1). Mark (0, 1) visited.

Step 4: Pop the max from the heap. The heap has (9, 1, 0) and (9, 0, 1) — both have sum 9. Pop either one, say (9, 1, 0). Record sum 9. Result = [10, 9]. Push neighbors:

  • (2, 0): sum = a[2] + b[0] = 2 + 6 = 8. Push (8, 2, 0). Mark (2, 0) visited.
  • (1, 1): sum = a[1] + b[1] = 3 + 5 = 8. Push (8, 1, 1). Mark (1, 1) visited.

Step 5: Pop the max: (9, 0, 1). Record sum 9. Result = [10, 9, 9]. We have k = 3 results — done!

Result: [10, 9, 9]. We only examined 3 sums from the heap, plus pushed a few candidates. We never needed to generate all 16 possible pairs.

Max-Heap with Index Tracking — Explore Top-K Sums Efficiently — Watch how the max-heap always gives us the next largest sum combination, and we explore only the neighboring index pairs to find candidates.

Algorithm

  1. Sort array a in descending order.
  2. Sort array b in descending order.
  3. Create a max-heap and push the tuple (a[0] + b[0], 0, 0) — the sum of the two largest elements with their indices.
  4. Create a visited set and add index pair (0, 0).
  5. Initialize an empty result list.
  6. Repeat k times:
    a. Pop the maximum element (sum, i, j) from the heap.
    b. Append sum to the result.
    c. If (i+1, j) is within bounds and not visited, push (a[i+1] + b[j], i+1, j) into the heap and mark it visited.
    d. If (i, j+1) is within bounds and not visited, push (a[i] + b[j+1], i, j+1) into the heap and mark it visited.
  7. Return the result list.

Code

#include <vector>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

class Solution {
public:
    vector<int> topKSumPairs(vector<int>& a, vector<int>& b, int k) {
        int n = a.size();
        
        // Sort both arrays in descending order
        sort(a.rbegin(), a.rend());
        sort(b.rbegin(), b.rend());
        
        // Max-heap: stores {sum, {index_i, index_j}}
        priority_queue<pair<int, pair<int, int>>> maxHeap;
        set<pair<int, int>> visited;
        
        // Start with the largest possible pair
        maxHeap.push({a[0] + b[0], {0, 0}});
        visited.insert({0, 0});
        
        vector<int> result;
        
        while ((int)result.size() < k) {
            auto [sum, indices] = maxHeap.top();
            maxHeap.pop();
            auto [i, j] = indices;
            
            result.push_back(sum);
            
            // Push neighbor (i+1, j) if valid and unvisited
            if (i + 1 < n && visited.find({i + 1, j}) == visited.end()) {
                maxHeap.push({a[i + 1] + b[j], {i + 1, j}});
                visited.insert({i + 1, j});
            }
            
            // Push neighbor (i, j+1) if valid and unvisited
            if (j + 1 < n && visited.find({i, j + 1}) == visited.end()) {
                maxHeap.push({a[i] + b[j + 1], {i, j + 1}});
                visited.insert({i, j + 1});
            }
        }
        
        return result;
    }
};
import heapq

class Solution:
    def topKSumPairs(self, a: list[int], b: list[int], k: int) -> list[int]:
        n = len(a)
        
        # Sort both arrays in descending order
        a.sort(reverse=True)
        b.sort(reverse=True)
        
        # Max-heap (negate sums since Python has min-heap)
        # Store (-sum, i, j)
        max_heap = [(-(a[0] + b[0]), 0, 0)]
        visited = {(0, 0)}
        
        result = []
        
        while len(result) < k:
            neg_sum, i, j = heapq.heappop(max_heap)
            result.append(-neg_sum)
            
            # Push neighbor (i+1, j) if valid and unvisited
            if i + 1 < n and (i + 1, j) not in visited:
                heapq.heappush(max_heap, (-(a[i + 1] + b[j]), i + 1, j))
                visited.add((i + 1, j))
            
            # Push neighbor (i, j+1) if valid and unvisited
            if j + 1 < n and (i, j + 1) not in visited:
                heapq.heappush(max_heap, (-(a[i] + b[j + 1]), i, j + 1))
                visited.add((i, j + 1))
        
        return result
import java.util.*;

class Solution {
    public List<Integer> topKSumPairs(int[] a, int[] b, int k) {
        int n = a.length;
        
        // Sort both arrays in descending order
        Arrays.sort(a);
        Arrays.sort(b);
        // Reverse to get descending order
        for (int l = 0, r = n - 1; l < r; l++, r--) {
            int tmp = a[l]; a[l] = a[r]; a[r] = tmp;
            tmp = b[l]; b[l] = b[r]; b[r] = tmp;
        }
        
        // Max-heap: stores {sum, i, j}
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (x, y) -> y[0] - x[0]
        );
        Set<String> visited = new HashSet<>();
        
        // Start with the largest possible pair
        maxHeap.add(new int[]{a[0] + b[0], 0, 0});
        visited.add("0,0");
        
        List<Integer> result = new ArrayList<>();
        
        while (result.size() < k) {
            int[] top = maxHeap.poll();
            int sum = top[0], i = top[1], j = top[2];
            
            result.add(sum);
            
            // Push neighbor (i+1, j)
            String key1 = (i + 1) + "," + j;
            if (i + 1 < n && !visited.contains(key1)) {
                maxHeap.add(new int[]{a[i + 1] + b[j], i + 1, j});
                visited.add(key1);
            }
            
            // Push neighbor (i, j+1)
            String key2 = i + "," + (j + 1);
            if (j + 1 < n && !visited.contains(key2)) {
                maxHeap.add(new int[]{a[i] + b[j + 1], i, j + 1});
                visited.add(key2);
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n + k log k)

Sorting both arrays takes O(n log n) each, so O(n log n) total. The heap loop runs k times. In each iteration, we pop once (O(log k)) and push at most 2 elements (O(log k) each). So the heap operations cost O(k log k). Since k ≤ n, the sorting step dominates in the worst case, giving O(n log n) overall. If k is much smaller than n, the heap work is negligible.

Space Complexity: O(k)

The max-heap holds at most 2k elements at any time (each pop generates at most 2 pushes, and we pop k times). The visited set stores at most 3k entries. The result array stores k elements. So total extra space is O(k). This is a massive improvement over the O(n²) space of the brute force — for n = 10^5 and k = 100, we use 100 entries instead of 10 billion.