Last Updated: 24 Feb, 2021
Find Pair With Smallest Difference
Easy
Asked in companies
Given two unsorted arrays of non-negative integers, 'arr1' and 'arr2' of size 'N' and 'M', respectively. Your task is to find the pair of elements (one from each array), such that their absolute (non-negative) difference is the smallest, and return the difference.
Example :
N = 3, arr1 = [10, 20, 30]
M = 2, arr2 = [17, 15]
The smallest difference pair is (20, 17) with an absolute difference of 3. So, the answer is 3.
Note :
Both the arrays are unsorted, and all array elements are non-negative integers.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and 'M', where 'N' and 'm' are the sizes of array 'arr1' and 'arr2', respectively.
The second line of each test case contains 'N' space-separated integers denoting the elements of array 'arr1'.
The third line of each test case contains 'M' space-separated integers denoting the elements of array 'arr2'.
Output format :
For each test case, return the smallest absolute difference.
Note:
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N, M <= 1000
0 <= arr1[i], arr2[i] <=10^6
Time Limit: 1 second
Approaches
We can use two nested loops to iterate through all the possible ‘M * N’ pairs of values to calculate the smallest absolute difference among all the pairs.
- Initialize ‘minDiff = abs(arr1[0] - arr2[0])’. The ‘abs’ function returns the absolute value of given integer.
- Run of loop where ‘i’ ranges from ‘0’ to ‘M - 1’. Use this ‘i’ as the index of array 'arr1'.
- Run a nested loop where ‘j’ ranges from ‘0’ to ‘N - 1’. Use this ‘j’ as the index of array 'arr2'.
- If ‘minDiff’ is greater than ‘abs(arr1[i] - arr2[j])’ then ‘minDiff = abs(arr1[i] - arr2[j])’.
- Run a nested loop where ‘j’ ranges from ‘0’ to ‘N - 1’. Use this ‘j’ as the index of array 'arr2'.
- Return ‘minDiff’ as the answer.
Sort arrays 'arr1' and 'arr2' in ascending order. Let ‘i’ be the pointer to the first element of 'arr1', ‘j’ be the pointer to the first element of 'arr2', and ‘minDiff’ store the final answer.
Store the current difference i.e. ‘abs(arr1[i] - arr2[j])’ in ‘minDiff’. Assuming that ‘arr2[j]’ is greater than ‘arr1[i]’, then incrementing ‘j’ will only increase the difference between ‘arr2[j]’ and ‘arr1[i]’. Therefore we need to increment ‘i’, and update ‘minDiff’ if it’s greater than the new difference. We have to iterate until one of the arrays is completely traversed. For each iteration, update ‘minDiff’ and increment the index with the smaller array value.
- Sort the arrays 'arr1' and 'arr2' in ascending order.
- Initialize ‘i = 0’, ‘j = 0’ and ‘minDiff = abs(arr1[0] - arr2[0])’.
- Run a while loop until ‘i’ is less than 'N' and ‘j’ is less than 'M'.
- If ‘abs(arr1[i] - arr2[j])’ is less than ‘minDiff’ update ‘minDiff = abs(arr1[i] - arr2[j])’.
- If ‘arr1[i]’ is less than ‘arr2[j]’ increment ‘i’, else increment ‘j’.
- Return ‘minDiff’ as the answer.