K-pairs with smallest sum in 2 arrays

February 2, 2021

K-pairs with smallest sum in 2 arrays

K-pairs with smallest sum in 2 arrays In Java.

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.

Examples: 

Input : arr1[ ] = {1, 7, 11} 

arr2[ ] = {2, 4, 6}

k = 3

Output : [1, 2], [1, 4], [1, 6]

Explanation: The first 3 pairs are returned from the sequence [1, 2], [1, 4], [1, 6], [7, 2], [7, 4], [11, 2], [7, 6], [11, 4], [11, 6]

ALGORITHM:

  • Check for null conditions.

  • Create a 2d List with values based on the given elements.

  • Sort the pairs according to Sum.

  • Return the Sublist of the list till K.

Java code :

class prepinsta {
    public List<List<Integer>> kPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if(nums1 == null || nums2 == null ||nums1.length ==0 || nums2.length ==0)
            return ans;
        
        for(int i=0; i<nums1.length; i++)
        {
            for(int j=0; j<nums2.length; j++)
            {
            List<Integer> row = new ArrayList<Integer>();
            row.add(nums1[i]);
            row.add(nums2[j]);
            ans.add(row);    
            }
        }
        
        Collections.sort(ans, (x,y)-> (x.get(0)+x.get(1)) – (y.get(0) + y.get(1)));
        if(k < ans.size())
            ans = ans.subList(0,k);
        return ans;
    }
}
Output:

Input :  arr1[] = {1, 7, 11}
         arr2[] = {2, 4, 6}
         k = 3
Output : [1, 2],
         [1, 4],
         [1, 6]