## Find The Minimum Difference

### October 15, 2013

This is rather straight forward, though I admit it took a few tries to get all the less thans and minus signs in the right place:

```(define (f xs ys)   (let ((d (- (car xs) (car ys))))     (let loop ((xs xs) (ys ys) (diff (abs d)))       (cond ((or (null? xs) (null? ys)) diff)             ((< (car xs) (car ys))               (let ((d (- (car ys) (car xs))))                 (loop (cdr xs) ys (min d diff))))             (else (let ((d (- (car xs) (car ys))))                     (loop xs (cdr ys) (min d diff))))))))```

For example:

```> (f '(19 22 24) '(37 38 49 88)) 13```

The difference of 13 appears between 24 of the first array and 37 of the second array.

Assuming that the longer of the two arrays has length n, the algorithm given above has time complexity O(n). If the arrays weren’t sorted, you could sort them and then scan, giving a O(n log n) algorithm, or you could compare the items one-by-one for an O(n2) algorithm.

You can run the program at http://programmingpraxis.codepad.org/4bWj9XMf.

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