Minimum Absolute Difference
Problem
Given an array of distinct integers, return all pairs [a, b] (a < b) whose absolute difference equals the minimum absolute difference of any two elements. The pairs must be returned in ascending order.
arr = [4, 2, 1, 3][[1, 2], [2, 3], [3, 4]]def minimum_abs_difference(arr):
arr.sort()
best = min(arr[i] - arr[i-1] for i in range(1, len(arr)))
return [[arr[i-1], arr[i]] for i in range(1, len(arr)) if arr[i] - arr[i-1] == best]function minimumAbsDifference(arr) {
arr.sort((a, b) => a - b);
let best = Infinity;
for (let i = 1; i < arr.length; i++) best = Math.min(best, arr[i] - arr[i - 1]);
const out = [];
for (let i = 1; i < arr.length; i++) if (arr[i] - arr[i - 1] === best) out.push([arr[i - 1], arr[i]]);
return out;
}class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
int best = Integer.MAX_VALUE;
for (int i = 1; i < arr.length; i++) best = Math.min(best, arr[i] - arr[i - 1]);
List<List<Integer>> out = new ArrayList<>();
for (int i = 1; i < arr.length; i++)
if (arr[i] - arr[i - 1] == best) out.add(List.of(arr[i - 1], arr[i]));
return out;
}
}vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
sort(arr.begin(), arr.end());
int best = INT_MAX;
for (int i = 1; i < (int)arr.size(); i++) best = min(best, arr[i] - arr[i - 1]);
vector<vector<int>> out;
for (int i = 1; i < (int)arr.size(); i++)
if (arr[i] - arr[i - 1] == best) out.push_back({arr[i - 1], arr[i]});
return out;
}Explanation
The key realization is that the two numbers with the smallest difference must be neighbors once the array is sorted. If they weren't adjacent, something would sit between them, and that something would be even closer to one of them.
So step one is to sort the array. Then we only need to look at adjacent pairs, never every possible pair.
We make two passes over the sorted array. The first finds best, the smallest adjacent gap. The second collects every adjacent pair whose gap equals best. Because the array is sorted, those pairs naturally come out in ascending order.
Example: [4,2,1,3] sorts to [1,2,3,4]. Every neighbor differs by 1, so best = 1.
All three adjacent pairs match, giving [[1,2],[2,3],[3,4]]. Sorting turns an O(n^2) pair search into a quick linear scan.