1200. Minimum Absolute Difference

Problem Description

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, where each pair [a, b] satisfies:

• a, b are from arr
• a < b
• b - a equals the minimum absolute difference of any two elements in arr

Solution: Sorting

The most efficient approach involves sorting the input array. Sorting allows us to easily find the minimum absolute difference by simply comparing adjacent elements. Once we have the minimum difference, we can iterate through the sorted array again to identify all pairs with that difference.

Algorithm:

1. Sort the array: Sort the input array arr in ascending order. This step enables efficient calculation of minimum difference between adjacent elements.

2. Find the minimum absolute difference: Iterate through the sorted array, calculating the absolute difference between consecutive elements. Keep track of the minimum difference found so far.

3. Collect pairs with minimum difference: Iterate through the sorted array again. If the difference between consecutive elements equals the minimum difference found in step 2, add the pair as a list to the result list.

Time Complexity: The dominant operation is the sorting of the array, which takes O(n log n) time using efficient algorithms like merge sort or quicksort, where 'n' is the length of the input array. The subsequent iterations are linear, O(n), making the overall time complexity O(n log n).

Space Complexity: The space complexity depends on the sorting algorithm used. In-place sorting algorithms like quicksort can have O(log n) space complexity due to the recursion stack. Merge sort typically requires O(n) extra space. The space used for the result list is at most O(n) in the worst case (all pairs have minimum difference). Therefore, the overall space complexity is O(n) or O(n log n) depending on the sorting algorithm.

Code Implementation (Python):

from itertools import pairwise
 
class Solution:
    def minimumAbsDifference(self, arr: list[int]) -> list[list[int]]:
        arr.sort()
        min_diff = float('inf')  # Initialize with positive infinity
 
        #Find minimum difference
        for a, b in pairwise(arr):
            min_diff = min(min_diff, b - a)
 
        #Collect pairs with minimum difference
        result = [[a, b] for a, b in pairwise(arr) if b - a == min_diff]
        return result

Code Implementation (Java):

import java.util.*;
 
class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < arr.length; i++) {
            minDiff = Math.min(minDiff, arr[i] - arr[i - 1]);
        }
 
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] == minDiff) {
                List<Integer> pair = new ArrayList<>();
                pair.add(arr[i - 1]);
                pair.add(arr[i]);
                result.add(pair);
            }
        }
        return result;
    }
}

Code Implementation (C++):

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
 
using namespace std;
 
class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int minDiff = numeric_limits<int>::max(); 
        for (size_t i = 1; i < arr.size(); ++i) {
            minDiff = min(minDiff, arr[i] - arr[i - 1]);
        }
 
        vector<vector<int>> result;
        for (size_t i = 1; i < arr.size(); ++i) {
            if (arr[i] - arr[i - 1] == minDiff) {
                result.push_back({arr[i - 1], arr[i]});
            }
        }
        return result;
    }
};

These code examples demonstrate the core logic of the solution. The specific syntax and data structures might vary slightly depending on the programming language used, but the underlying algorithm remains consistent. Note that the Python solution uses itertools.pairwise for a concise iteration over pairs of consecutive elements. In other languages, a manual loop is typically used for this.