Last Updated: 9 Dec, 2020
K Max Sum Combinations
Easy
Asked in companies
You are given two arrays/lists ‘A’ and ‘B’ of size ‘N’ each. You are also given an integer ‘K’. You must return ‘K’ distinct maximum and valid sum combinations from all the possible sum combinations of the arrays/lists ‘A’ and ‘B’.
Sum combination adds one element from array ‘A’ and another 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 contains two integers, ‘N’ and ‘K’, denoting the length of the array/list and the number of required sum combinations respectively.
The second line contains ‘N’ space-separated integers denoting the array ‘A’ elements.
The third line contains ‘N’ space-separated integers denoting the array ‘B’ elements.
Output Format :
Return the maximum ‘K’ valid sum combinations in descending order.
Note :
You don’t have to print anything; it has already been handled. Just implement the function.
Approaches
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’.
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.
- 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’)).
- Finally, return the output array ‘RESULT’.
Similar problems