See the original problem on HackerRank.
Solutions
The brute force solution consists in calculating the absolute difference of each
pair and reducing to the minimum value. This takes \(O(N^2)\).
We can find better solution, instead, by making a simple observation: the
closest two numbers, the lowest their difference. It’s just like calculating the
distance between points on the same axis. Indeed, the formula to calculate the
distance between two points \(x1, x2\) on the same axis is simply
\(|x1-x2|\).
Thus, we need to “fill the gaps” between numbers. This means, we need to sort
the array. Then, we do the difference between each adjacent pair and calculate
the minimum value along the way.
Here is a possible implementation in Python 2:
1
2
3
4
5
6
|
def minimumAbsoluteDifference(arr, n):
arr.sort()
minVal = sys.maxint
for i in range(n - 1):
minVal = min(minVal, abs(arr[i] - arr[i+1]))
return minVal
|
A pattern brings out from the code above: zip | map | reduce:
1
2
3
|
def minimumAbsoluteDifference(arr, n):
arr.sort()
return min(map(lambda x: abs(x[0]-x[1]), zip(arr[1:], arr)))
|
The same approach in C#, by Claudio Bacchelli:
1
2
3
4
5
|
static int minimumAbsoluteDifference(int[] arr)
{
var lista = arr.ToList.Sort();
return lista.Zip(lista.Skip(1), (a, b) => Math.Abs(a - b)).Min();
}
|
An alternative way of writing the solution above in Python 3 by Eduard “Eddie”
Rubio Cholbi and Stefano Ligabue:
1
2
3
|
def minimumAbsoluteDifference(arr):
arr = sorted(arr)
return min(map(lambda a, b: b - a, arr[:-1], arr[1:]))
|
Eddie and Stefano wrote generic way of to zip things in Python and applied it to
the problem:
1
2
3
4
5
6
7
|
def zipper(arr, n):
return (arr[i:len(arr)-n+i+1] for i in range(n))
# Complete the minimumAbsoluteDifference function below.
def minimumAbsoluteDifference(arr):
arr = sorted(arr)
return min(map(lambda a, b: b - a, *zipper(arr, 2)))
|
zipper zips a sequence with itself shifted n times.
For example, on arr = [1,2,3,4,5]:
With n=1 (does nothing):
1
2
|
unzipper(arr, 1)
=> [1, 2, 3, 4, 5]
|
With n=2:
1
2
3
|
unzipper(arr, 2)
=> [1, 2, 3, 4]
[2, 3, 4, 5]
|
With n=3:
1
2
3
4
|
unzipper(arr, 2)
=> [1, 2, 3]
[2, 3, 4]
[3, 4, 5]
|
Etc.
This is an example of “freely expressing oneself” we encourage at Coding Gym.
Eddie and Stefano solved the challenge very quickly and started experimenting
with their favourite language, getting out of their “state of the art”. Since
Coding Gym is not time nor prize driven, anyone sets her own targets.
Just for fun, in C++ zip|map|reduce can be written in terms of inner_product:
1
2
3
4
5
|
sort(begin(v), end(v));
cout << inner_product(next(begin(v)), end(v), begin(v), numeric_limits<int>::max(),
[](int a, int b) { return min(a,b); },
[](int a, int b) { return abs(a-b); }
);
|
In C++20 we can use ranges, left as an exercise.
In Haskell we can write the whole program (input parsing included) in 125
characters.
1
2
3
|
import Data.List
f=minimum.(zipWith(\a b->abs(a-b))<*>tail).sort
main=interact(show.f.(fmap read).words.head.(drop 1).lines)
|
But it’s better explained by this code:
1
2
3
4
5
6
7
8
9
10
11
|
import Data.List
minAbsDiff xs = minimum diffs
where
absDiff x y = abs (x - y)
diffs = zipWith absDiff (tail sorted) sorted
sorted = sort xs
parseInput = (fmap read) . words . head . (drop 1) . lines
main = interact $ show . minAbsDiff . parseInput
|
In the compact version above alepez used function
composition to create a point-free version of the minAbsDiff function.
Point-free functions are just functions which do not mention the actual
arguments they will be applied to.
We can also implement it with foldl:
1
2
3
4
|
f xs = foldl op 10000000000 $ zip sorted (tail sorted)
where
sorted = sort xs
op a (x, y) = min a (abs (x - y))
|
We can also implement innerProduct like C++:
1
2
3
4
5
6
|
f xs = innerProduct min (\x y -> abs (x - y)) 10000000000 ys (tail ys)
where
ys = sort xs
innerProduct op1 op2 init xs ys =
foldl (\a (x, y) -> op1 a (op2 x y)) init (zip xs ys)
|
A solution in Scala by benny1693:
1
2
|
def minimumAbsoluteDifference(arr: Array[Int]): Int =
(arr.sorted zip arr.sorted.tail).map({case (a,b) => abs(a-b)}).min
|
A solution in Python 3 by Massimo Dalla Cia:
1
2
3
4
5
6
7
8
9
10
11
12
|
def minimumAbsoluteDifference(arr):
arr.sort(key=int)
sort_array = arr
delta = 999999999
for i in range(1, len(sort_array)):
if delta > abs(sort_array[i] - sort_array[i-1] ):
delta = abs(sort_array[i] - sort_array[i-1])
return int(delta)
|
A solution in Python 3 by ranzatoweb:
1
2
3
|
def minimumAbsoluteDifference(arr):
s_arr = sorted(arr)
return min(map(lambda x: abs(x[0] - x[1]), zip(s_arr,s_arr[1:])))
|
A solution in Python 3 by Enrico Lovisotto:
1
2
3
4
|
def minimumAbsoluteDifference(arr):
s_arr = sorted(arr)
diffs = map(lambda c: abs(c[0] - c[1]), zip(s_arr, s_arr[1:]))
return sorted(diffs)[0]
|