See the original problem on HackerRank.
Solutions
Wait! Have you challenged yourself with this problem? If yes, click here to show the solution.The brute force solution consists in calculating the absolute difference of each pair and reducing to the minimum value. This takes O(N2).
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:
|
|
A pattern brings out from the code above: zip | map | reduce:
|
|
The same approach in C#, by Claudio Bacchelli:
|
|
An alternative way of writing the solution above in Python 3 by Eduard “Eddie” Rubio Cholbi and Stefano Ligabue:
|
|
Eddie and Stefano wrote generic way of to zip things in Python and applied it to the problem:
|
|
zipper
zips a sequence with itself shifted n
times.
For example, on arr = [1,2,3,4,5]
:
With n=1
(does nothing):
With n=2
:
With n=3
:
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
:
|
|
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.
|
|
But it’s better explained by this code:
|
|
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
:
|
|
We can also implement innerProduct
like C++:
|
|
A solution in Scala by benny1693
:
|
|
A solution in Python 3 by Massimo Dalla Cia:
|
|
A solution in Python 3 by ranzatoweb:
|
|
A solution in Python 3 by Enrico Lovisotto:
|
|