Problem

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

Examples

Example 1:

1
2
3

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:

1
2

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

Example 3:

1
2

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

Similar Problem

Count Number of Pairs With Absolute Difference K

Solution

Method 1 - Sorting

Here are the steps:

  1. Sort the Array: Sorting the array helps in finding the minimum absolute difference between adjacent elements.
  2. Find Minimum Difference: Iterate through the sorted array to find the smallest difference between any two adjacent elements.
  3. Collect Pairs: Iterate through the sorted array again to collect all pairs of elements that have the minimum absolute difference.

Code

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

public class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr); // Sort the array
        int minDiff = Integer.MAX_VALUE;
        List<List<Integer>> result = new ArrayList<>();

        // Find the minimum difference between adjacent elements
        for (int i = 1; i < arr.length; i++) {
            int diff = arr[i] - arr[i - 1];
            if (diff < minDiff) {
                minDiff = diff;
                result.clear(); // Reset result list
                result.add(Arrays.asList(arr[i - 1], arr[i]));
            } else if (diff == minDiff) {
                result.add(Arrays.asList(
                    arr[i - 1], arr[i])); // Add pair to result list
            }
        }

        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def minimum_abs_difference(arr):
    arr.sort()  # Sort the array
    min_diff = float("inf")
    result = []

    # Find the minimum difference between adjacent elements
    for i in range(1, len(arr)):
        diff = arr[i] - arr[i - 1]
        if diff < min_diff:
            min_diff = diff
            result =[[arr[i - 1], arr[i]]]  # Reset result list
        elif diff == min_diff:
            result.append([arr[i - 1], arr[i]])  # Add pair to result list

    return result

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting step
  • 🧺 Space complexity: O(n), due to the list used to store the result pairs.