Home
Refer
Jobs
Alumni
Resume
Notifications

Given two unsorted arrays of integers, write a program to find a pair of elements (one from each array) whose sum is minimum. The program should have a time complexity of O(n log n) or less.

🚀 Best Answers Get Featured in our LinkedIn Community based on Your Consent, To Increase Your Chances of Getting Interviewed. 🚀

Interview Answer:

One way to approach the problem is to sort both arrays in ascending order. We can then start with the first element of the first array and the last element of the second array. We calculate the sum of these two elements and compare it with the minimum sum we have seen so far. If the sum is smaller than the current minimum, we update our result. We then move either to the next element of the first array or the previous element of the second array based on whether the sum was less than or greater than the target sum. We repeat this process until we find the pair with the minimum sum.

This algorithm has a time complexity of O(n log n) because sorting both arrays takes O(n log n) time and iterating through both arrays once takes O(n) time.

Here is the Java implementation of the algorithm:

             public static int[] findPairWithMinSum(int[] arr1, int[] arr2) {
Arrays.sort(arr1);
Arrays.sort(arr2);
int i = 0, j = arr2.length - 1;
int[] result = {
arr1[0], arr2[arr2.length - 1] }
;
int minSum = arr1[0] + arr2[arr2.length - 1];
while (i < arr1.length && j >= 0) {
int sum = arr1[i] + arr2[j];
if (sum < minSum) {
minSum = sum;
result[0] = arr1[i];
result[1] = arr2[j];
}
if (sum <= minSum && i < arr1.length - 1) {
i++;
}
else {
j--;
}
}
return result;
}

Some relevant citations on sorting algorithms:

© 2024 Referral Solutions, Inc. Incorporated. All rights reserved.