Minimum Absolute Difference

Difficulty: Easy | Acceptance: 75.10% | Paid: No Topics: Array, Sorting

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 each pair) and sorted in ascending order by the first element.

• Examples
• Constraints
• Brute Force
• Sorting

Examples

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

Brute Force

Intuition Compare every possible pair of elements in the array to find the smallest absolute difference. Then, iterate through all pairs again to collect those that match this minimum difference.

Steps

• Initialize min_diff to infinity.
• Use two nested loops to calculate the absolute difference between every pair (i, j) where i < j. Update min_diff if a smaller difference is found.
• Initialize an empty result list.
• Use two nested loops again to find all pairs where the absolute difference equals min_diff.
• Sort the result list to satisfy the output ordering requirements.

class Solution:
    def minimumAbsDifference(self, arr: list[int]) -> list[list[int]]:
        n = len(arr)
        min_diff = float('inf')
        
        # Find the minimum absolute difference
        for i in range(n):
            for j in range(i + 1, n):
                diff = abs(arr[i] - arr[j])
                if diff < min_diff:
                    min_diff = diff
        
        res = []
        # Collect all pairs with the minimum difference
        for i in range(n):
            for j in range(i + 1, n):
                if abs(arr[i] - arr[j]) == min_diff:
                    if arr[i] < arr[j]:
                        res.append([arr[i], arr[j]])
                    else:
                        res.append([arr[j], arr[i]])
        
        res.sort()
        return res

Complexity

• Time: O(n²)
• Space: O(1) (excluding output space)
• Notes: This approach is simple but inefficient for large inputs due to the nested loops.

Sorting

Intuition If the array is sorted, the minimum absolute difference between any two elements must occur between adjacent elements. This allows us to find the minimum difference in a single pass.

Steps

• Sort the array in ascending order.
• Initialize min_diff to infinity.
• Iterate through the sorted array once to find the minimum difference between adjacent elements (arr[i+1] - arr[i]).
• Iterate through the array a second time. If the difference between adjacent elements equals min_diff, add the pair [arr[i], arr[i+1]] to the result list.
• Since the array is sorted, the result list will automatically be in the correct order.

class Solution:
    def minimumAbsDifference(self, arr: list[int]) -> list[list[int]]:
        arr.sort()
        min_diff = float('inf')
        
        # Find the minimum difference between adjacent elements
        for i in range(len(arr) - 1):
            diff = arr[i+1] - arr[i]
            if diff < min_diff:
                min_diff = diff
        
        res = []
        # Collect pairs with the minimum difference
        for i in range(len(arr) - 1):
            if arr[i+1] - arr[i] == min_diff:
                res.append([arr[i], arr[i+1]])
        
        return res

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on the sorting algorithm’s space complexity.
• Notes: This is the optimal approach for this problem.