











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]
Login/Signup to comment