Problem Description

Given an array of integers arr, your task is to find all pairs of elements with the minimum absolute difference between any two elements in the array. Return a list of pairs (each pair is a list of two integers) sorted in ascending order.

• Each pair [a, b] should satisfy a < b.
• The returned list of pairs should be sorted based on the first element, then the second.
• All pairs with the minimum absolute difference should be included; do not reuse elements except as allowed by their positions in the original array.
• Constraints typically are:
  • 2 <= arr.length <= 10^5
  • -10^6 <= arr[i] <= 10^6

Example:
Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]

Thought Process

The naive way to solve this problem would be to check every possible pair of elements in the array, compute their absolute differences, and find the minimum. However, this approach is inefficient for large arrays because it requires checking all possible pairs, resulting in a time complexity of O(n²).

To optimize, we can take advantage of the fact that the smallest absolute difference between any two numbers in a list occurs between two adjacent numbers in a sorted array. Imagine lining up the numbers in order; the closest numbers will be next to each other. This means we only need to compare each number to its neighbor after sorting, rather than every possible pair.

By recognizing this property, we shift from a brute-force approach to a much more efficient one, leveraging sorting and single-pass comparison.

Solution Approach

Let's break down the optimized solution step by step:

1. Sort the array arr in ascending order.
   • This ensures that the smallest differences are between adjacent elements.
2. Initialize a variable to track the minimum absolute difference.
   • Set it to a very large value initially (like infinity).
3. Iterate through the sorted array, comparing each pair of adjacent elements.
   • For each pair, compute the absolute difference.
   • If this difference is less than the current minimum, update the minimum and reset the list of pairs.
   • If the difference equals the current minimum, append this pair to the list.
4. Return the list of pairs with the minimum absolute difference.
   • Because the array is sorted, pairs will naturally be in the required order.

This approach is efficient because sorting is O(n log n), and the single pass through the array is O(n).

Example Walkthrough

Let's use the sample input: arr = [4, 2, 1, 3]

1. Sort the array: [1, 2, 3, 4]
2. Compute differences:
   • |2 - 1| = 1
   • |3 - 2| = 1
   • |4 - 3| = 1
   The minimum difference is 1.
3. Collect pairs:
   • [1, 2]
   • [2, 3]
   • [3, 4]
4. Return: [[1, 2], [2, 3], [3, 4]]

At each step, we only need to look at adjacent elements, ensuring both efficiency and correctness.

Code Implementation

class Solution:
    def minimumAbsDifference(self, arr):
        arr.sort()
        min_diff = float('inf')
        result = []
        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]]]
            elif diff == min_diff:
                result.append([arr[i - 1], arr[i]])
        return result
      

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int minDiff = INT_MAX;
        vector<vector<int>> result;
        for (int i = 1; i < arr.size(); ++i) {
            int diff = arr[i] - arr[i - 1];
            if (diff < minDiff) {
                minDiff = diff;
                result.clear();
                result.push_back({arr[i - 1], arr[i]});
            } else if (diff == minDiff) {
                result.push_back({arr[i - 1], arr[i]});
            }
        }
        return result;
    }
};
      

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            int diff = arr[i] - arr[i - 1];
            if (diff < minDiff) {
                minDiff = diff;
                result.clear();
                result.add(Arrays.asList(arr[i - 1], arr[i]));
            } else if (diff == minDiff) {
                result.add(Arrays.asList(arr[i - 1], arr[i]));
            }
        }
        return result;
    }
}
      

var minimumAbsDifference = function(arr) {
    arr.sort((a, b) => a - b);
    let minDiff = Infinity;
    let result = [];
    for (let i = 1; i < arr.length; i++) {
        let diff = arr[i] - arr[i - 1];
        if (diff < minDiff) {
            minDiff = diff;
            result = [[arr[i - 1], arr[i]]];
        } else if (diff === minDiff) {
            result.push([arr[i - 1], arr[i]]);
        }
    }
    return result;
};
      

Time and Space Complexity

Brute-force approach:
- Time Complexity: O(n²), because it checks every possible pair.
- Space Complexity: O(n), for storing the result pairs.

Optimized approach (sorting + single pass):

• Time Complexity: O(n log n) due to sorting, plus O(n) for the single pass through the array, so overall O(n log n).
• Space Complexity: O(n) in the worst case, for storing the result pairs (if all adjacent differences are the same).

The optimized approach is much more efficient and suitable for large input sizes.

Summary

By recognizing that the minimum absolute difference in an array occurs between adjacent elements in the sorted order, we can reduce the problem to sorting and a single pass comparison. This strategy is both elegant and efficient, leveraging the properties of sorted arrays to avoid unnecessary computations. The key insight is to sort first, then only check adjacent pairs, making the solution both simple and powerful.