Find Pair With Smallest Difference

Posted: 24 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1

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])’.
  • Return ‘minDiff’ as the answer.
Try Problem