K Max Sum Combinations — Asked in Walmart Interview

Problem Statement :

Given two arrays/lists ‘A’ and ‘B’ of size ’N’ each. You are also given an integer ‘K’ and 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’.

Sample Input:

A : [1, 3]
B : [4, 2]
K : 2

Sample Output:

7 5

Explanation of Sample Test Case :

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, 5.

Approach :

Time Complexity : O(NlogN)
Space Complexity : O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.