Solution: K Maximum Sum Combinations From Two Arrays

Statement

You are given two integer arrays, arr1 and arr2, each of size $n$. You are also given an integer k. Your task is to return the k largest sum combinations that can be formed by adding one element from arr1 and one element from arr2, for all possible pairs (arr1[i] + arr2[j]), where $0 ≤ i, j < n$.

Note: The output should be sorted in non-increasing order.

Constraints:

• $1 ≤ n ≤ 1000$

• $1\leq$ arr1[i], arr2[i] $\leq 10^3$

• $1 ≤$ k $≤ n$

Solution

The essence of the solution lies in identifying the top k maximum sum combinations of both input arrays using the top k elements pattern. Instead of generating all possible sum combinations (which would result in a quadratic time complexity), the solution uses a max heap to dynamically compute the largest sum combinations. The solution begins by sorting both input arrays in descending order. This ensures that the largest sums can be calculated by combining elements from the beginning of both arrays. The max heap stores these combinations along with their index pairs, while a visited set is used to prevent processing duplicate index pairs.

The key operation involves extracting the largest sum from the heap and then considering the next two potential sum combinations: $arr1[i+1] + arr2[j]$, which moves right in arr1 while keeping the element in arr2 fixed, and $arr1[i] + arr2[j+1]$, which moves right in arr2 while keeping the element in arr1 fixed. These two combinations are pushed into the heap, but only if the index pairs $(i+1, j)$ and $(i, j+1)$ haven’t been visited before to avoid duplicate processing. If the index pairs have already been visited, they are ignored. By iterating k times, the solution extracts the largest sums and continues to explore the next best combinations until k maximum sums are found. Once the k sums are extracted, the result list is returned in non-increasing order.

Now, let’s look at the solution steps below:

1. We start by sorting arrays, arr1 and arr2, in descending order.

2. We initialize a max heap, pq, to store the possible sum combinations and the indexes of the elements contributing to each sum. The sum of the first elements from both arrays (arr1[0] + arr2[0]) is pushed into the heap, along with their respective indexes (0, 0).

3. We use a visited set to keep track of the pairs of indexes that have already been processed, preventing duplicate combinations.

4. We also initialize an empty list, result, to store the output of the top k maximum sum combinations..

5. We then iterate k times to extract the top k largest sum combinations. In each iteration:

   1. We extract the largest sum combination from the heap with its corresponding indexes, and add the sum to result.

   2. We generate the next possible sum combinations by considering the following:

      1. Moving to the next element in arr1 while keeping the extracted index of arr2 (i+1, j) the same. If this combination is valid (i.e., the index exists and hasn’t been visited before), it’s pushed to the heap and marked as visited.

      2. Moving to the next element in arr2 while keeping the extracted index of arr1 (i, j+1) the same. Similarly, if this combination is valid and not yet visited, it’s pushed to the heap and marked as visited.

6. We continue this process until k combinations have been added to the result array.

7. Finally, we return the result array, containing the k maximum sum combinations in non-increasing order.

Let’s look at the following illustration to get a better understanding of the solution: