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]))
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]
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]
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)
Top comments (0)