## 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

xbe any integer in the first array andybe any integer in the second array. Find min(abs(x−y)); 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.

Advertisements

Pages: 1 2

In Python:

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

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

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

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:

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`

.Sorry for spamming, but here’s a slightly cleaner version of my

`mad`

function: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))

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.

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[0]-arr2[0])

for(i in arr1){

for(j in arr2){

def diff = Math.abs(i-j)

if(min>diff){

min=diff

}

}

}

return min

}

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 ⍬

∞

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).

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;

}

A shorter haskell solution

import Control.Monad

minDiff (x:xs) (y:ys) | x – y < 0 = choose (y-x) $ minDiff xs (y:ys)

| otherwise = choose (x-y) $ minDiff (x:xs) ys

where choose x m = fmap (min x) m `mplus` Just x

minDiff _ _ = Nothing