K Max Sum Combinations

Easy
0/40
Average time to solve is 10m
profile
Contributed by
58 upvotes
Asked in companies
WalmartInfo Edge India (Naukri.com)D.E.Shaw

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
3 2
1 3 5
6 4 2
Sample Output 1 :
11 9
Explanation of Sample Output 1 :
For the given arrays/lists, all the possible sum combinations are: 
7(1 + 6), 5(1 + 4), 3(1 + 2), 9(3 + 6), 7(3 + 4), 5(3 + 2), 11(6 + 5), 9(5 + 4), 7(5 + 2).

The two maximum sum combinations from the above combinations are 11 and 9.
Sample Input 2 :
2 1
1 1
1 1
Sample Output 2 :
2
Explanation of sample input 2 :
For the given arrays/lists, two possible sum combinations are 2(1 + 1), and 2(1 + 1).
Constraints :
1 <= N <= 100
1 <= K <= N
-10^5 <= A[i], B[i] <= 10^5

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

Time limit: 1 sec
Hint

Can you think about generating all the possible sum combinations?

Approaches (2)
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 :

 

  1. Create an array/list ‘tempArray’ of size ('N' * ‘N’).
  2. 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’.
  3. Sort the ‘tempArray’ in descending order.
  4. After the above process, ‘tempArray’ will contain all the valid max sum combinations in decreasing order.
  5. Return the first ‘K’ elements of ‘tempArray’.
Time Complexity

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)).

Space Complexity

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). 

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
K Max Sum Combinations
Full screen
Console