Minimum Absolute Difference in an Array
The absolute difference is the positive difference between two values a and b, is written |a-b| or |b-a| and they are equal. If a=3 and b=2, |3-2| = |2-3| = 1. Given an array of integers, find the minimum absolute difference between any two elements in the array.
Example. arr = [-2,2,4]
There are 3 pairs of numbers: [-2,2], [-2,4] and [4,2]. The absolute differences for these pairs are |-2-2| = 4,|-2-4| = 6 and |2-4| = 2. The minimum absolute difference is 2.
Sample Input 0
3
3 -7 0
Sample Output 0
3
Explanation 0
The first line of input is the number of array elements. The array, arr = [3, -7, 0] There are three pairs to test: (3, -7), (3,0) and (-7,0). The absolute differences are:
- |3 – -7| = 10
- |3 – 0| = 3
- |-7 – 0| = 7
Remember that the order of values in the subtraction does not influence the result. The smallest of these absolute differences is .
Sample Input 1
10
-59 -36 -13 1 -53 -92 -2 -96 -54 75
Sample Output 1
1
Explanation 1
The smallest absolute difference is |-54 – -53| = 1.
Sample Input 2
5
1 -3 71 68 17
Sample Output 2
3
Explanation 2
The minimum absolute difference is |71 – 68| = 3.
Step 1 : – Template Implementation
There are two types of two pointer templates.
1). Opposite direction two pointer template
2). Same direction two pointer template
Based on our analysis of the Minimum Absolute Difference in an array problem statement, this is a non-target-based problem where we need to find the minimum absolute difference between adjacent elements. Therefore, we will use the base structure of the same direction pointers template and as per the approach sort the list with Collections sort() method.
class Result {
public static int minimumAbsoluteDifference(List<Integer> arr) {
int minDiff = Integer.MAX_VALUE;
Collections.sort(arr);
int left = 0;
int right = 1;
while (right < arr.size()) {
//code
left++;
right++;
}
return minDiff;
}
}Step 2 : – I/O parameters.
This step calculates the difference between two consecutive elements (arr.get(right) – arr.get(left)) since the array is already sorted, ensuring the result is always non-negative. Then, it updates minDiff with the smallest difference found so far using Math.min(minDiff, diff).
class Result {
public static int minimumAbsoluteDifference(List<Integer> arr) {
int minDiff = Integer.MAX_VALUE;
Collections.sort(arr);
int left = 0;
int right = 1;
while (right < arr.size()) {
int diff = arr.get(right) - arr.get(left);
minDiff = Math.min(minDiff, diff);
left++;
right++;
}
return minDiff;
}
}Final Code : –
class Result {
public static int minimumAbsoluteDifference(List<Integer> arr) {
int minDiff = Integer.MAX_VALUE;
Collections.sort(arr);
int left = 0;
int right = 1;
while (right < arr.size()) {
int diff = arr.get(right) - arr.get(left);
minDiff = Math.min(minDiff, diff);
left++;
right++;
}
return minDiff;
}
}