Problem

Submissions

Hints & solutions

Discuss

Find Pair With Smallest Difference

Easy

0/40

Average time to solve is 15m

Contributed by

24 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample input 1 :

Sample output 1 :

1
3

Explanation For Sample Input 1 :

Test Case 1 :
The smallest difference pairs are (7, 6) and (5, 6) with an absolute difference of 1, so the answer is 1.

Test Case 2 :
The smallest difference pair is (20, 17) with an absolute difference of 3, so the answer is 3.

Sample input 2 :

2
4 4
1 5 12 3
16 9 10 20
2 4
20 10
10 13 19 16

Sample output 2 :

2
0

Hint 1

Hint 2

Iterate over all the possible pairs and find the pair with the smallest absolute difference.

Approaches (2)

Approach 1

Approach 2

Brute force

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.

Time Complexity

O(M * N), where 'N' and 'M' are sizes of arrays 'arr1' and 'arr2', respectively.

The outer loop runs 'N' times, and the inner loop runs 'M' times, so the total number of iterations is ‘M * N’. Hence, the time complexity ‘O(M * N)’.

Space Complexity

O(1)

Since we are not using any extra space, space complexity is constant.

(100% EXP penalty)

Find Pair With Smallest Difference

Console