Minimum Absolute Difference in an Array

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 ajacent 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)))

Just for fun, the same pattern in C++ 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); }
);