# Minimum Absolute Difference
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-absolute-difference)
Canonical: https://scaleengineer.com/dsa/problems/minimum-absolute-difference
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [PayPal](https://scaleengineer.com/companies/paypal), [Paycom](https://scaleengineer.com/companies/paycom), [Audible](https://scaleengineer.com/companies/audible)
---
## 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`

**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 equal to 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 <= 105`
* `-106 <= arr[i] <= 106`

# Approaches
## Brute Force Approach
This approach involves a straightforward, brute-force method of comparing every possible pair of elements in the array. For each pair, we calculate the absolute difference and keep track of the minimum difference found so far. We store all pairs that match this minimum difference.
**Time:** O(N^2). The nested loops result in comparing every pair of elements, which is N * (N-1) / 2 comparisons. This quadratic complexity makes it too slow for the given constraints. · **Space:** O(N), in the worst-case scenario where many pairs have the same minimum difference (e.g., for an input like `[1, 2, 3, 4]`, the result has `N-1` pairs). This space is used to store the result list.
**Pros:** Simple to understand and implement.; Does not require modifying the original array (if a copy is made).
**Cons:** Highly inefficient due to the O(N^2) time complexity.; Will likely result in a 'Time Limit Exceeded' error for large input arrays as specified in the constraints.
### Explanation
In this method, we iterate through the array with two nested loops to generate every unique pair of numbers. We maintain a variable, `minDifference`, to store the smallest absolute difference encountered. As we iterate, we compare the difference of the current pair with `minDifference`.

If the current pair's difference is smaller than `minDifference`, we've found a new minimum. We update `minDifference`, clear our result list (as all previously found pairs are now invalid), and add the current pair to the result list. If the current pair's difference is equal to `minDifference`, we simply add it to our result list.

Because the pairs are added as they are found, the final list of pairs is not guaranteed to be in ascending order. Therefore, a final sorting step is required on the result list before returning it.

```java
import java.util.*;

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int minDifference = Integer.MAX_VALUE;
        List<List<Integer>> resultPairs = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int diff = Math.abs(arr[i] - arr[j]);

                if (diff < minDifference) {
                    minDifference = diff;
                    resultPairs.clear();
                    List<Integer> pair = new ArrayList<>();
                    pair.add(Math.min(arr[i], arr[j]));
                    pair.add(Math.max(arr[i], arr[j]));
                    resultPairs.add(pair);
                } else if (diff == minDifference) {
                    List<Integer> pair = new ArrayList<>();
                    pair.add(Math.min(arr[i], arr[j]));
                    pair.add(Math.max(arr[i], arr[j]));
                    resultPairs.add(pair);
                }
            }
        }

        // Sort the final list of pairs as required
        Collections.sort(resultPairs, (a, b) -> a.get(0).compareTo(b.get(0)));

        return resultPairs;
    }
}
```
### Algorithm
- Initialize a variable `minDifference` to a very large value (e.g., `Integer.MAX_VALUE`).
- Initialize an empty list of lists, `resultPairs`, to store the final pairs.
- Use a nested loop structure. The outer loop iterates from `i = 0` to `n-1` and the inner loop from `j = i + 1` to `n-1`.
- For each pair `(arr[i], arr[j])`, calculate the absolute difference `currentDifference = Math.abs(arr[i] - arr[j])`.
- If `currentDifference` is less than `minDifference`:
  - Update `minDifference` with `currentDifference`.
  - Clear the `resultPairs` list.
  - Add the current pair, sorted as `[min(arr[i], arr[j]), max(arr[i], arr[j])]`, to `resultPairs`.
- If `currentDifference` is equal to `minDifference`:
  - Add the current pair, sorted, to `resultPairs`.
- After iterating through all pairs, sort the `resultPairs` list based on the first element of each pair.
- Return `resultPairs`.

## Sorting-based Approach
A much more efficient approach is to first sort the array. The key insight is that the minimum absolute difference between any two elements in the array will always occur between two adjacent elements in the sorted array. This reduces the problem from comparing all O(N^2) pairs to just O(N) adjacent pairs.
**Time:** O(N log N). The dominant operation is sorting the array. The subsequent single pass to find the minimum difference and collect pairs takes O(N) time. Therefore, the total time complexity is O(N log N). · **Space:** O(N). The space complexity of the sorting algorithm (`Arrays.sort` in Java for primitives) is O(log N) on average for the recursion stack. However, the space required for the output list can be up to O(N) in the worst case. Thus, the overall space complexity is dominated by the output list, making it O(N).
**Pros:** Highly efficient with a time complexity of O(N log N), which passes the given constraints.; The logic is clean and relies on a powerful property of sorted sequences.; The resulting list of pairs is naturally sorted, avoiding an explicit sorting step on the final list.
**Cons:** The primary cost is the initial sort, which might not be ideal if the array is already partially sorted or if sorting is expensive for other reasons.; The space complexity for sorting can be O(N) in some language implementations, although it's often O(log N).
### Explanation
The logic behind this approach is that for any three numbers `a < b < c`, the difference `c - a` is equal to `(c - b) + (b - a)`. Since both `(c - b)` and `(b - a)` are positive, `c - a` must be greater than both `b - a` and `c - b`. This property implies that we only need to check the differences between adjacent elements after sorting the array to find the global minimum difference.

The algorithm proceeds as follows:
1. Sort the input array `arr`.
2. Make a single pass through the sorted array, from the first to the second-to-last element.
3. During the pass, keep track of the minimum difference found so far. If we find a pair of adjacent elements with a difference smaller than the current minimum, we update the minimum and clear our result list, adding this new pair. If we find a pair with a difference equal to the current minimum, we just add it to the result list.

This single-pass approach after sorting is efficient and ensures the final list of pairs is already sorted, as we process the elements in increasing order.

```java
import java.util.*;

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        // 1. Sort the array
        Arrays.sort(arr);

        List<List<Integer>> resultPairs = new ArrayList<>();
        int minDifference = Integer.MAX_VALUE;

        // 2. Single pass to find min difference and collect pairs
        for (int i = 0; i < arr.length - 1; i++) {
            int currentDifference = arr[i+1] - arr[i];

            if (currentDifference < minDifference) {
                minDifference = currentDifference;
                resultPairs.clear();
                resultPairs.add(Arrays.asList(arr[i], arr[i+1]));
            } else if (currentDifference == minDifference) {
                resultPairs.add(Arrays.asList(arr[i], arr[i+1]));
            }
        }

        return resultPairs;
    }
}
```
### Algorithm
- First, sort the input array `arr` in ascending order.
- Initialize a variable `minDifference` to `Integer.MAX_VALUE`.
- Initialize an empty list of lists, `resultPairs`.
- Iterate through the sorted array from `i = 0` to `n-2` (i.e., up to the second-to-last element).
- In each iteration, calculate the difference between adjacent elements: `currentDifference = arr[i+1] - arr[i]`.
- Compare `currentDifference` with `minDifference`:
  - If `currentDifference < minDifference`, a new minimum is found. Update `minDifference`, clear `resultPairs`, and add the current pair `[arr[i], arr[i+1]]`.
  - If `currentDifference == minDifference`, add the current pair `[arr[i], arr[i+1]]` to `resultPairs`.
- After the loop, return `resultPairs`. No final sorting is needed as pairs are added in ascending order.

# Solutions
### Java

```java
class Solution { public List < List < Integer >> minimumAbsDifference ( int [] arr ) { Arrays . sort ( arr ); int n = arr . length ; int mi = 1 << 30 ; for ( int i = 0 ; i < n - 1 ; ++ i ) { mi = Math . min ( mi , arr [ i + 1 ] - arr [ i ]); } List < List < Integer >> ans = new ArrayList <>(); for ( int i = 0 ; i < n - 1 ; ++ i ) { if ( arr [ i + 1 ] - arr [ i ] == mi ) { ans . add ( List . of ( arr [ i ], arr [ i + 1 ])); } } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < vector < int >> minimumAbsDifference ( vector < int >& arr ) { sort ( arr . begin (), arr . end ()); int mi = 1 << 30 ; int n = arr . size (); for ( int i = 0 ; i < n - 1 ; ++ i ) { mi = min ( mi , arr [ i + 1 ] - arr [ i ]); } vector < vector < int >> ans ; for ( int i = 0 ; i < n - 1 ; ++ i ) { if ( arr [ i + 1 ] - arr [ i ] == mi ) { ans . push_back ({ arr [ i ], arr [ i + 1 ]}); } } return ans ; } };
```

### Python

```python
class Solution : def minimumAbsDifference ( self , arr : List [ int ]) -> List [ List [ int ]]: arr . sort () mi = min ( b - a for a , b in pairwise ( arr )) return [[ a , b ] for a , b in pairwise ( arr ) if b - a == mi ]
```