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(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.
Programming Praxis 
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 # 57In 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 diffWhile 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:
import Data.Maybe (fromJust) mad :: [Integer] -> [Integer] -> Maybe Integer mad [] _ = Nothing mad _ [] = Nothing 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/0returnsInfinity, but this isn’t anInteger.Sorry for spamming, but here’s a slightly cleaner version of my
madfunction:mad :: [Integer] -> [Integer] -> Maybe Integer mad [] _ = Nothing mad _ [] = Nothing 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)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.
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))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).
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; }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