Skip to content

1200. Minimum Absolute Difference

Description

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 <= 105
  • -106 <= arr[i] <= 106

Solutions

Solution 1: Sorting

Thinking

Enumerating all pairs is \(O(n^2)\), which is too slow for \(n \le 10^5\).

After sorting, the gap between any two values is at least the sum of adjacent gaps between them, so the global minimum absolute difference occurs only between neighbors.

We therefore sort \(arr\), scan adjacent differences for the minimum \(mi\), then collect every adjacent pair whose difference equals \(mi\). Sorting shrinks the candidate set; the two linear passes compute the extremum and gather the answer.

According to the problem description, we need to find the minimum absolute difference between any two elements in the array \(arr\). Therefore, we can first sort the array \(arr\), then traverse the adjacent elements to get the minimum absolute difference \(mi\).

Finally, we traverse the adjacent elements again to find all pairs of elements where the minimum absolute difference equals \(mi\).

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array \(arr\).

1
2
3
4
5
class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        mi = min(b - a for a, b in pairwise(arr))
        return [[a, b] for a, b in pairwise(arr) if b - a == mi]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        int mi = 1 << 30;
        for (int i = 0; i < n - 1; ++i) {
            mi = Math.min(mi, arr[i + 1] - arr[i]);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i + 1] - arr[i] == mi) {
                ans.add(List.of(arr[i], arr[i + 1]));
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int mi = 1 << 30;
        int n = arr.size();
        for (int i = 0; i < n - 1; ++i) {
            mi = min(mi, arr[i + 1] - arr[i]);
        }
        vector<vector<int>> ans;
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i + 1] - arr[i] == mi) {
                ans.push_back({arr[i], arr[i + 1]});
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func minimumAbsDifference(arr []int) (ans [][]int) {
    sort.Ints(arr)
    mi := 1 << 30
    n := len(arr)
    for i := 0; i < n-1; i++ {
        if t := arr[i+1] - arr[i]; t < mi {
            mi = t
        }
    }
    for i := 0; i < n-1; i++ {
        if arr[i+1]-arr[i] == mi {
            ans = append(ans, []int{arr[i], arr[i+1]})
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function minimumAbsDifference(arr: number[]): number[][] {
    arr.sort((a, b) => a - b);
    let mi = 1 << 30;
    const n = arr.length;
    for (let i = 0; i < n - 1; ++i) {
        mi = Math.min(mi, arr[i + 1] - arr[i]);
    }
    const ans: number[][] = [];
    for (let i = 0; i < n - 1; ++i) {
        if (arr[i + 1] - arr[i] === mi) {
            ans.push([arr[i], arr[i + 1]]);
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
    pub fn minimum_abs_difference(mut arr: Vec<i32>) -> Vec<Vec<i32>> {
        arr.sort();
        let n = arr.len();

        let mut mi = i32::MAX;
        for i in 1..n {
            mi = mi.min(arr[i] - arr[i - 1]);
        }

        let mut ans = Vec::new();
        for i in 1..n {
            if arr[i] - arr[i - 1] == mi {
                ans.push(vec![arr[i - 1], arr[i]]);
            }
        }

        ans
    }
}

Comments