The Minimum Absolute Difference Algorithm of an Array

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements. Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr
a < b
b – a equals to the minimum absolute difference of any two elements in arr

Example 1:
Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:
Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:
Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:
2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

Hints:
Find the minimum absolute difference between two elements in the array.
The minimum absolute difference must be a difference between two consecutive elements in the sorted array.

Finding Minimum Absolute Difference in a Sorted Array

Of course, we can bruteforce the array for each possible pair, and then we can compare and record the minimum pairs that have the smallest absolute difference values. However, this cost O(N^2), which is not the most efficient algorithm.

If we sort the array (which we can, in O(NLogN) time), then we can do another O(N) loop to compare only the adjacent elements because there is no need to compare non-neighbour pairs as they will not be the smallest minimum absolute difference pair.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        vector<vector<int>> r;
        sort(begin(arr), end(arr));        
        int D = INT_MAX;
        for (int i = 1; i < arr.size(); ++ i) {
            int d = arr[i] - arr[i - 1];
            if (d < D) {
                r.clear();
                D = d;
                r.push_back({arr[i - 1], arr[i]});
            } else if (d == D) {
                r.push_back({arr[i - 1], arr[i]});
            }
        }        
        return r;
    }
};

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        vector<vector<int>> r;
        sort(begin(arr), end(arr));        
        int D = INT_MAX;
        for (int i = 1; i < arr.size(); ++ i) {
            int d = arr[i] - arr[i - 1];
            if (d < D) {
                r.clear();
                D = d;
                r.push_back({arr[i - 1], arr[i]});
            } else if (d == D) {
                r.push_back({arr[i - 1], arr[i]});
            }
        }        
        return r;
    }
};

Then, if the current difference value is smaller, then we clear the result vector, record the minimum value, and push the current pair. If we find a equal pair, we simply push it to the back of the result vector. O(1) constant space is required.

–EOF (The Ultimate Computing & Technology Blog) —