Minimum Absolute Difference - Solution & Explanation

Problem Overview: You are given an integer array arr. The task is to find every pair of elements whose absolute difference is the smallest among all possible pairs. The result must include all pairs that share this minimum difference and should be returned in ascending order.

Approach 1: Complete Pairwise Comparison (Brute Force) (O(n²) time, O(1) space)

This method checks every possible pair in the array. Use two nested loops: the outer loop fixes an element and the inner loop compares it with every element after it. For each pair, compute abs(arr[i] - arr[j]) and keep track of the smallest difference found so far. If a smaller difference appears, reset the result list; if the difference matches the current minimum, append the pair.

This approach requires no extra data structures and works on the unsorted array. However, it performs n(n-1)/2 comparisons, which becomes expensive for large inputs. Brute force is still useful when explaining the baseline solution in interviews or when constraints are very small.

Approach 2: Sort and Find Minimum Difference (O(n log n) time, O(1) extra space)

Sorting reveals the key insight: the smallest absolute difference between any two numbers must appear between adjacent elements in a sorted array. After sorting the array, iterate once and compute the difference between neighboring elements arr[i] and arr[i+1]. Maintain the smallest difference seen and collect all pairs that match it.

This works because sorting orders numbers so that the closest values appear next to each other. There is no need to compare distant elements. The algorithm performs a single linear scan after the sort, making the dominant cost the sorting step. Many implementations perform the sort in-place, so the extra memory usage remains constant aside from the output list.

The technique combines ideas from sorting with sequential scanning on an array. The code stays simple while achieving strong performance, which is why this approach appears in most accepted solutions.

Recommended for interviews: Start by explaining the brute force comparison to demonstrate you understand the definition of the minimum absolute difference. Then pivot to the sorting insight. Interviewers typically expect the O(n log n) sorted approach because it reduces unnecessary comparisons and shows you can leverage ordering to simplify pair problems.