Minimum Absolute Difference — Solution in Python, Java & C++
Minimum Absolute Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Absolute Difference is an easy coding problem on arrays and sorting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference between them.
Return the pairs in ascending order, each pair written as [a, b] with a < b.
Example 1
Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum difference is 1.
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 <= 40-1000000 <= arr[i] <= 1000000All elements are distinct.
Hints for Minimum Absolute Difference
Hint 1
After sorting, the minimum difference must occur between adjacent elements.
Hint 2
One pass finds the minimum gap; a second collects every adjacent pair achieving it.
Hint 3
Sorting also gives the required output order for free.
How to solve Minimum Absolute Difference
After sorting, the minimum difference occurs between adjacent elements; find it, then collect every adjacent pair achieving it.
Approach
- Sort.
- Compute the minimum adjacent gap.
- Emit
[a[i-1], a[i]]for everyiwith that gap.
Why it works
Any two non-adjacent sorted elements bracket an adjacent pair with a gap no larger, so adjacent pairs suffice; sorted order also yields the required output order.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Values are distinct, so the gap is never zero.
Reference solution
Python
def minimumAbsDifference(arr):
ordered = sorted(arr)
best = min(ordered[i] - ordered[i - 1] for i in range(1, len(ordered)))
return [[ordered[i - 1], ordered[i]] for i in range(1, len(ordered))
if ordered[i] - ordered[i - 1] == best]Java
public static int[][] minimumAbsDifference(int[] arr) {
int[] s = arr.clone();
Arrays.sort(s);
int best = s[1] - s[0];
for (int i = 2; i < s.length; i++) best = Math.min(best, s[i] - s[i - 1]);
List<int[]> out = new ArrayList<>();
for (int i = 1; i < s.length; i++) {
if (s[i] - s[i - 1] == best) out.add(new int[]{s[i - 1], s[i]});
}
return out.toArray(new int[0][]);
}C++
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
vector<int> s = arr;
sort(s.begin(), s.end());
int best = s[1] - s[0];
for (int i = 2; i < (int) s.size(); i++) best = min(best, s[i] - s[i - 1]);
vector<vector<int>> out;
for (int i = 1; i < (int) s.size(); i++) {
if (s[i] - s[i - 1] == best) out.push_back(vector<int>{s[i - 1], s[i]});
}
return out;
}JavaScript
var minimumAbsDifference = function(arr) {
const sorted = arr.slice().sort(function(a, b) { return a - b; });
let best = Infinity;
for (let i = 1; i < sorted.length; i++) {
const d = sorted[i] - sorted[i - 1];
if (d < best) best = d;
}
const out = [];
for (let i = 1; i < sorted.length; i++) {
if (sorted[i] - sorted[i - 1] === best) out.push([sorted[i - 1], sorted[i]]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms