Minimum Absolute Difference

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

For example:

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.

arr = [1,3,6,10,15]

Output: [[1,3]]

arr = [3,8,-10,23,19,-4,-14,27]

Output: [[-14,-10],[19,23],[23,27]]

class Solution:
    def minimumAbsDifference(self, arr: list[int]) -> list[list[int]]:
        arr.sort()
        min_diff = float('inf')
        result = []

        for i in range(len(arr) - 1):
            diff = arr[i+1] - arr[i]
            if diff < min_diff:
                min_diff = diff
                result = [[arr[i], arr[i+1]]]]
            elif diff == min_diff:
                result.append([arr[i], arr[i+1]])

        return result

Naive Solution

The naive solution involves calculating the absolute difference between every pair of numbers in the array and keeping track of the minimum difference found so far. Then, iterate through all pairs again to collect those pairs with the minimum difference.

Optimal Solution

The optimal solution sorts the array first. After sorting, the minimum absolute difference can only occur between adjacent elements. Iterate through the sorted array and calculate the difference between adjacent elements. Keep track of the minimum difference found so far and the pairs that have that minimum difference.

Big(O) Run-time Analysis

• Sorting: O(n log n), where n is the length of the input array arr.
• Iteration: O(n) to find the minimum difference and collect pairs.
• Overall: O(n log n) due to the sorting step dominating the time complexity.

Big(O) Space Usage Analysis

• Sorting: In-place sorting algorithms like heapsort or quicksort can have O(log n) space complexity. If a sorting algorithm like merge sort is used, then O(n) space is required.
• Result List: In the worst case, the number of pairs with the minimum difference could be O(n), leading to O(n) space complexity.
• Overall: O(n) in the worst case, considering the space for the result list. If in-place sort is possible and the number of pairs is small, this could reduce to O(log n).

Edge Cases

1. Empty Array: If the input array is empty or has only one element, there are no pairs to form. The code should handle this gracefully, likely by returning an empty list.
2. Array with Duplicate Elements: The problem statement specifies distinct integers, but handling duplicates would involve modifying the condition diff < min_diff to diff <= min_diff and making sure to not add duplicate pairs to the result.
3. Large Input Array: For very large arrays, the space complexity could become a concern. Consider using an in-place sorting algorithm and optimizing memory usage for the result list.
4. Integer Overflow: When calculating the difference between two large integers, there's a possibility of integer overflow. Using a data type with a larger range (e.g., long in Java or int64 in Python) can help prevent this.