Watch 10 video solutions for Minimum Absolute Difference, a easy level problem involving Array, Sorting. This walkthrough by Nick White has 22,153 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 arra < bb - 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] <= 106Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Complete Pairwise Comparison (Brute Force) | O(n²) | O(1) | Useful for small arrays or when explaining the baseline idea before optimization. |
| Sort and Scan Adjacent Elements | O(n log n) | O(1) extra (excluding output) | Best general solution. Sorting ensures the closest values appear next to each other, reducing comparisons. |