DEV Community

Luciano Pinheiro
Luciano Pinheiro

Posted on • Updated on

HackerRank Minimum Absolute Difference

As you may know, HackerRank has a series of interview challenges varying from easy to hard. This challenge presented now is in the package Interview Preparation Kit > Greedy Algorithms and is considered easy.

It basically gives an array and you must check the absolute difference of every pair of numbers.

difference = []
for x in range(len(arr)):
    for y in range(x+1, len(arr)):
        difference.append(abs(arr[x], arr[y]))
Enter fullscreen mode Exit fullscreen mode

But there is a catch! If you simply check all numbers, you will check unnecessary numbers. It's much better if you just check a number with the nearest neighbors of it. For example if arr is

arr = [-59, -36, -13, 1, -53, -92, -2, -96, -54, 75]
Enter fullscreen mode Exit fullscreen mode

and if we sort it, we just need to check each number twice (or once in the case of extremities)

arr.sort()
print(arr) # [-96, -92, -59, -54, -53, -36, -13, -2, 1, 75]
Enter fullscreen mode Exit fullscreen mode

Now we clearly see for example that we just need to test -36 with -53 and -13. It's not possible that the sub-array [-96, -92, -59, -54] have a smaller difference with -36 than -53.

The complete algorithms is this:

def minimumAbsoluteDifference(arr):
    arr.sort()
    differences = []
    for x in range(len(arr) - 1):
        differences.append(abs(arr[x] - arr[x + 1]))
    return min(differences)
Enter fullscreen mode Exit fullscreen mode

Top comments (0)