K Max Sum Combinations
You are given two arrays/lists ‘A’ and ‘B’ of size ‘N’ each. You are also given an integer ‘K’. You have to find the ‘K’ maximum and valid sum combinations from all the possible sum combinations of the arrays/lists ‘A’ and ‘B’.

Sum combination is made by adding one element from array ‘A’ and another element from array ‘B’.

For example :

A : [1, 3] B : [4, 2] K : 2 The possible sum combinations can be 5(3 + 2), 7(3 + 4), 3(1 + 2), 5(1 + 4). The 2 maximum sum combinations are 7 and 5.

Input Format :

The first line of input contains an integer 'T', denoting the number of test cases. The first line of every test case contains two integers ‘N’ and ‘K’ denoting the length of the array/list and the number of required sum combinations respectively. The second line of every test case contains ‘N’ space-separated integers denoting the elements of the array ‘A’. The third line of every test case contains ‘N’ space-separated integers denoting the elements of the array ‘B’.

Output Format :

For every test case, return the maximum ‘K’ valid sum combinations in descending order.

Note :

You don’t have to print anything; it has already been taken care of. Just implement the function.

Constraints :

1

Question

K Max Sum Combinations

You are given two arrays/lists ‘A’ and ‘B’ of size ‘N’ each. You are also given an integer ‘K’. You have to find the ‘K’ maximum and valid sum combinations from all the possible sum combinations of the arrays/lists ‘A’ and ‘B’.

Sum combination is made by adding one element from array ‘A’ and another element from array ‘B’.

For example :

A : [1, 3] 
B : [4, 2] 
K : 2
The possible sum combinations can be 5(3 + 2), 7(3 + 4), 3(1 + 2), 5(1 + 4). The 2 maximum sum combinations are 7 and 5.

Input Format :

The first line of input contains an integer 'T', denoting the number of test cases.

The first line of every test case contains two integers ‘N’ and ‘K’ denoting the length of the array/list and the number of required sum combinations respectively. 

The second line of every test case contains ‘N’ space-separated integers denoting the elements of the array ‘A’.

The third line of every test case contains ‘N’ space-separated integers denoting the elements of the array ‘B’.

Output Format :

For every test case, return the maximum ‘K’ valid sum combinations in descending order.

Note :

You don’t have to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 5
1 <= N <= 100
1 <= K <= N
-10^5 <= A[i], B[i] <= 10^5

Where 'A[i]' and 'B[i]' denotes the ith element in the given arrays/lists. 

Time limit: 1 sec

Accepted Answer

Brute

Generate all the possible sum combinations using two loops. Store the sum of all the sum combinations in an array/list and sort the array/list in descending order.

Finally, return the ‘K’ max sub-combinations from that array/list.

The Steps are as follows :

Create an array/list ‘tempArray’ of size ('N' * ‘N’).
Traverse the given arrays using two loops.
- In the outer loop, traverse the given array/list ‘A’ and select an element from it.
- In the inner loop, traverse the given array/list ‘B’ and select an element from it.
- Insert the sum of selected elements in the ‘tempArray’.
Sort the ‘tempArray’ in descending order.
After the above process, ‘tempArray’ will contain all the valid max sum combinations in decreasing order.
Return the first ‘K’ elements of ‘tempArray’.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), Where N is the number of elements in the given arrays/lists.

Since we are using an array of size (N ^ 2) to store the sum of combinations. This is the additional space required by the algorithm. Thus, the space complexity will be O(N ^ 2).

Time Complexity: OtherExplanation:

O((N ^ 2) * log(N ^ 2)), Where ‘N’ is the number of elements in the given arrays/lists.

For every element of an array, we are traversing all the elements of the other array. This requires (N ^ 2) time. After that, we are sorting the array of size (N ^ 2) which requires O((N ^ 2) * log(N ^ 2)) time. Thus, the total time complexity will be O((N ^ 2) * log(N ^ 2)).

Python (3.5)

"""
	Time Complexity: O((N ^ 2) * log(N ^ 2))
	Space Complexity: O(N ^ 2)

	Where 'N' is the number of elements the given arrays.
"""

def kMaxSumCombination(a, b, n, k):
	# Array to store all the possible sum combinations.
	tempArray = []
	
	# Loop to traverse the array 'A'.
	for i in range(n):
		# Loop to traverse the array 'B'.
		for j in range(n):
			currentSum = a[i] + b[j]
			
			# Add the sum of current combination .
			tempArray.append(currentSum)
		
	# Sort the array in descending order.
	tempArray.sort(reverse=True)
	
	# Return the first 'K' values.
	result = tempArray[:k]
	return result

C++ (g++ 5.4)

/*
	Time Complexity: O((N ^ 2) * log(N ^ 2))
	Space Complexity: O(N ^ 2)

	Where 'N' is the number of elements the given arrays.
*/

#include

vector kMaxSumCombination(vector &a, vector &b, int n, int k){
	// Array to store all the possible sum combinations.
	vectortempArray;
	
	// Loop to traverse the array 'A'.
	for(int i = 0; i < n; i++){
		// Loop to traverse the array 'B'.
		for(int j = 0; j < n; j++){
			int currentSum = a[i] + b[j];
			// Add the sum of current combination .
			tempArray.push_back(currentSum);
		}
	}
	// Sort the array in descending order.
	sort(tempArray.begin(), tempArray.end(), greater()); 
	
	// Return the first 'K' values.
	vector result(tempArray.begin(), tempArray.begin() + k);
	return result;
}

Java (SE 1.8)

/*
	Time Complexity: O((N ^ 2) * log(N ^ 2))
	Space Complexity: O(N ^ 2)

	Where 'N' is the number of elements the given arrays.
*/

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
	public static ArrayList kMaxSumCombination(ArrayList a, ArrayList b, int n, int k) {
		// Array to store all the possible sum combinations.
		ArrayListtempArray = new ArrayList();

		// Loop to traverse the array 'A".
		for (int i = 0; i < n; i++) {
			// Loop to traverse the array 'B'.
			for (int j = 0; j < n; j++) {
				int currentSum = a.get(i) + b.get(j);
				// Add the sum of current combination.
				tempArray.add(currentSum);
			}
		}
		// Sort the array in descending order.
		Collections.sort(tempArray, Collections.reverseOrder());

		// Return the first 'K' values.
		ArrayList result = new ArrayList();
		result.addAll(tempArray.subList(0, k));

		return result;
	}
}

Accepted Answer

Using Heap

In this approach, instead of exploring all the possible sum combinations, we will only use the sum-combinations that can be the possible candidates for the ‘K’ max sum combinations.

The idea is to sort both arrays and insert the possible candidates of max sum combinations into the max-heap. We will also use a set to make sure that we are using a sum-combination only once. Now, we will keep removing the max element(max sum combination) and keep inserting the next possible candidate in the max heap until we get ‘K’ max sum combinations. We will also store the indices corresponding to the value so that we will be able to get the next possible candidate pair.

The Steps are as follows :

Sort both the arrays/lists, array/list ‘A’ and array/list ‘B’.
Create a max-heap to store the sum combinations along with the indices of the elements from both arrays/lists ‘A’ and ‘B’ which make up the sum. The max heap is ordered by the sum, the max sum will be the root of the heap.
Initialize the heap with the maximum possible sum combination i.e ('A[N – 1]' + ‘B[N – 1]’ where ‘N’ is the size of array) and with the indices of elements from both the arrays ('N' – 1, 'N' – 1) because this will be maximum sum possible pair sum. The tuple inside the max heap will be ('A[N-1]' + 'B[N – 1]', ('N' – 1, ‘N’ – 1)). The max heap is ordered by the first value i.e sum of both elements.
Create an array/list ‘result’ of size ‘K’ that will store the ‘K’ max sum combinations.
We will keep processing the below steps until we do not get ‘K’ sum combinations.
- Remove the root of the max-heap to get the current largest sum and along with the indices of the element that make up the sum. Let the tuple be (sum, ('i', ‘j’)).
  - Add the ‘sum’ to the output array ‘RESULT’.
  - If the indices ('i' – 1, ‘j’) and ('i', ‘j’ – 1) are valid and not present in the set, insert ('A[i – 1]' + ‘B[j]’, ('i' – 1, ‘j’)) and ('A[i]' + ‘B[j – 1]’,('i', ‘j’ – 1)) into the max heap. This will make sure that the sum combinations are not redundant.
  - Insert the indices ('i' – 1, ‘j’) and ('i', ‘j’ – 1) into the set.
Finally, return the output array ‘RESULT’.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of elements in the given arrays/lists.

Since we are using a max-heap and a set. In the worst case, the total additional space will be O(N). Thus, the space complexity will be O(N).

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), Where ‘N’ is the number of elements in the array.

Since we are sorting the given arrays/lists which takes O(N * log(N)) time. Then, we are using a max-heap which, in the worst case, can contain ‘N’ elements. The operations on heap will require O(N * log(N)) time. The look-up in the set can be done in log(N) time. Thus, the time complexity will be O(N * log(N)).