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.

Solution (with less efficiency)

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        minimum = abs(max(arr)) - (min(arr))
        u = minimum
        for r in arr:
            for t in arr:
                if r - t != 0:
                    minimum = abs(r - t)
                    if minimum < u:
                        u = minimum
                    else:
                        minimum = minimum
        result = []
        for i in arr:
            for x in arr:
                if x != i and abs(i - x) == u and [x, i] not in result and [i, x] not in result:
                    h = [i, x]
                    h.sort()
                    result.append(h)
                    result.sort()
        return result
                    

CodePudding user response：

It should be obvious that sorting the list will place the elements that are closest together next to eachother. Sorting is generally a O(n log n) operation.

arr.sort()

Finding the minimum requires a single pass to compare neighboring elements. Pretty much any way you do it will be O(n). A very simple implementation would be

x = iter(arr)
next(x)
min_dist = min(b - a for a, b in zip(arr, x))

An even simpler one:

min_dist = min(arr[i   1] - arr[i] for i in range(len(arr) - 1))

Getting the pairs is now a matter of checking whether any of the differences in any of the generators used to compute min_diff are equal to min_diff. This is clearly also a O(n) operation.

pairs = [arr[i:i   2] for i in range(len(arr) - 1) if arr[i   1] - arr[i] == min_diff]

Since the complexity of the sort dominates, the overall algorithm is O(n log n), which is likely optimal, and certainly better than the existing O(n^2) implementation.

As @luk2302 suggests in a comment, you can avoid the second pass by accumulating pairs with the current minimum value as you go:

arr.sort()
if len(arr) < 2: return []
pairs = [arr[:2]]
current_minimum = arr[1] - arr[0]
for i in range(2, len(arr)):
    z = arr[i - 1:i   1]
    if (n := z[1] - z[0]) < current_minimum:
        pairs = [z]
        current_minimum = n
    elif n == current_minimum:
        pairs.append(z)