## Find The Minimum Difference

### October 15, 2013

We have today another exercise from our limitless supply of interview questions:

You are given two arrays of integers, where the integers do not repeat, the two arrays have no common integers, and both arrays are sorted in ascending order.

Let x be any integer in the first array and y be any integer in the second array. Find min(abs(xy)); i.e., find the smallest difference between any integers in the two arrays.

Your task is to write a program to find the smallest difference. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 14 Responses to “Find The Minimum Difference”

1. mattharrison86 said

```def find_smallest array1, array2
min = Float::INFINITY
array1.each_with_index { |elem1,i|
array2.each_with_index{ |elem2, j|
diff = (elem1 - elem2).abs
min = diff unless diff > min
}
}
min
end

puts find_smallest array1, array2 # 57
```
2. Paul said

In Python:

```def min_abs(arrx, arry):
itx, ity = iter(arrx), iter(arry)
x, y = next(itx, None), next(ity, None)
diff = float("inf")
while not None in (x, y):
diff = min(diff, abs(x - y))
if x < y:
x = next(itx, None)
else:
y = next(ity, None)
return diff
```
3. Graham said

While this won’t change the average complexity, can’t we shortcircuit if we find an absolute difference of zero?

4. Paul said

We can shortcuit if we find a difference of one. Zero is not possible, as the arrays do not have common numbers.

5. Graham said

Thanks @Paul, I didn’t read carefully enough!

6. Graham said

I hate to be a pain, but it’s not clear to me that the arrays have to be nonempty.
Here’s a Haskell version that handles empty lists as well:

```import Data.Maybe (fromJust)

mad :: [Integer] -> [Integer] -> Maybe Integer
mad xs ys = Just \$ m xs ys z
where
z = abs . head \$ zipWith (-) xs ys
m [] _ d = d
m _ [] d = d
m (a:as) (b:bs) d | d' == 1   = 1
| a < b     = m as (b:bs) d'
| otherwise = m (a:as) bs d'
where
d' = min d (abs \$ a - b)

main :: IO ()
main = mapM_ (print . uncurry mad) [([], [1..]),
([1..], []),
([19, 22, 24], [37, 28, 49, 88])]
```

This could have been cleaner if infinity were included in the integers in Haskell;
it’s true that `1/0` returns `Infinity`, but this isn’t an `Integer`.

7. Graham said

Sorry for spamming, but here’s a slightly cleaner version of my `mad` function:

```mad :: [Integer] -> [Integer] -> Maybe Integer
mad (x:xs) (y:ys) = Just \$ m xs ys (abs \$ x - y)
where
m [] _ d = d
m _ [] d = d
m (a:as) (b:bs) d | d' == 1   = 1
| a < b     = m as (b:bs) d'
| otherwise = m (a:as) bs d'
where
d' = min d (abs \$ a - b)
```
8. Mike said

Python version. Like Paul’s, but i put the iterators in a separate generator that returns potential minimum pairs from the lists. Then maxdiff() is straight forward.

def pairs(xs, ys):
itx, ity = iter(xs), iter(ys)
x, y = next(itx), next(ity)
while True:
yield x, y
x, y = (next(itx),y) if x < y else (x, next(ity))

def mindiff(xs, ys):
return min(abs(x – y) for x,y in pairs(xs, ys))

9. Mike said

Sorry, forgot the formating.

Python version. Like Paul’s, but i put the iterators in a separate generator that returns potential minimum pairs from the lists. Then maxdiff() is straight forward.

```

def pairs(xs, ys):
itx, ity = iter(xs), iter(ys)
x, y = next(itx), next(ity)
while True:
yield x, y
x, y = (next(itx),y) if x < y else (x, next(ity))

def mindiff(xs, ys):
return min(abs(x – y) for x,y in pairs(xs, ys))

```
10. Eric said

Here is my solution in groovy. I have a feeling there is a more efficient way to do this especially with the the def min at the start.

static int minDiff(arr1, arr2){
def min = Math.abs(arr1-arr2)
for(i in arr1){
for(j in arr2){
def diff = Math.abs(i-j)
if(min>diff){
min=diff
}
}
}
return min
}

11. Most of this stuff is well over my head, but I happen to be just starting to learn APL and so could’t resist. Using the example input from the first solution:

f←{⌊/⌊/|⍺∘.-⍵}
x←19 22 24
y←37 38 49 88
x f y
13

I don’t kow if there’s a clever mathy way to make it more efficient, but at least it has the virtue of simplicity. I guess this will run in O(n^2)… :-)

As for empty vectors, I am not sure what the subtraction operator should yield without any arguments, but I get infinity when I feed it to my function:

⍬ f ⍬

12. The Man From SQL said

Here’s my version in C#. As a small optimization for large arrays, I’ve added a short-circuit that exits if the difference between x and y-currrent is positive and greater than the abs difference between x and y-previous (since the arrays are guaranteed to be sorted, this means we won’t find a smaller difference for x).

```        public static int Find(int[] FirstArray, int[] SecondArray)
{
int minimum = Int32.MaxValue;
int lastDiff;

for (int i = 0; i < FirstArray.Length; i++)
{
lastDiff = Int32.MaxValue;

for (int j = 0; j < SecondArray.Length; j++)
{
int unAbsResult = SecondArray[j] - FirstArray[i];
int result = Math.Abs(unAbsResult);
if (result < minimum)
{
minimum = result;
}
if (result > lastDiff && unAbsResult > 0)
{
break;
}

lastDiff = result;
}
}
return minimum;
}
```
13. Dakshin said

Here is my version in C++:

#include
#include
#include
#include
#include
using namespace std;
#define N 10

struct small {
int diff;
int x;
int i;
int y;
int j;
} ;

int get_num();
int ascending(int *, int);

int main(){

int j,i=0;
int n=N;
int x[N];
int y[N];
int status;
struct small sm;
sm.x=sm.y=sm.i=sm.j=0;
sm.diff=1000;

while(i<n){
x[i++] = get_num();
}
cout<<"X:"<<endl;
for(i=0;i<n;i++)
cout<<' '<<x[i];
cout<<' '<<endl;

i=0;
while(i<n){
int num = get_num();
status = false;

for(j=0;j<n&&num==x[j];j++)
status =true;

if(status == false)
y[i++]
=num;

}

cout<<"Y:"<<endl;
for(i=0;i<n;i++)
cout<<' '<<y[i];
cout<<endl;

cout<<"After ascending:"<<endl;
ascending(x,n);
cout<<"X:"<<endl;
for(i=0;i<n;i++)
cout<<' '<<x[i];
cout<<endl;

ascending(y,n);
cout<<"Y:"<<endl;
for(i=0;i<n;i++)
cout<<' '<<y[i];
cout<<endl;

for(i=0;i<n;i++)
for(j=0;j<n;j++) {

if(abs(x[i]-y[j]) <sm.diff)
{
sm.diff=abs(x[i]-y[j]);
sm.i=i;
sm.j=j;
sm.x=x[i];
sm.y=y[j];
}

}

cout<<"diff:"<<sm.diff<<endl;
cout<<"nums:"<<sm.x<<' '<<sm.y<<endl;

return 0;
}

int get_num(){

num:

int n = rand()%100;

if(n!=0)
return n;
else
goto num;
}

int ascending(int *num, int n){

int temp=0;
int j,i=0;

for(i=0;i<n;i++)
for(j=0;jnum[j+1]){
temp=num[j];
num[j]=num[j+1];
num[j+1]=temp;
}

}

return true;
}

14. jozefg said