You are given an unsorted array of integers, write a Java program or function to find the minimum absolute difference between any two elements of the given array. For example,
If {5, -3, 7, -2} is the given array then possible pairs of elements and their absolute difference is,
(5, -3) = 5 – (-3) = 8
(5, 7) = 5 – 7 = 2
(5, -2) = 5 – (-2) = 7
(-3, 7) = -3 – 7 = 10
(-3, -2) = -3 – (-2) = 1
(7, -2) = 7 – (-2) = 9
So, minimum absolute difference of the given array is 1 between pairs (-3, -2).
Interchanging the positions of elements will not effect the result as we are calculating absolute difference.
Note : Absolute value means signs are ignored, only value is considered.
1. With Sorting:
This method is most efficient one. It gives time complexity of O(nlogn). In this method, first we sort the given array and then find absolute difference between adjacent pairs.
import java.util.Arrays;
public class JavaArrayProgram
{
private static void minimumAbsoluteDifference(int[] inputArray)
{
Arrays.sort(inputArray);
int minimum = Math.abs(inputArray[1] - inputArray[0]);
int firstElement = inputArray[0];
int secondElement = inputArray[1];
for (int i = 2; i < inputArray.length; i++)
{
if(Math.abs(inputArray[i] - inputArray[i-1]) < minimum)
{
minimum = Math.abs(inputArray[i] - inputArray[i-1]);
firstElement = inputArray[i-1];
secondElement = inputArray[i];
}
}
System.out.println("Sorted Input Array : "+Arrays.toString(inputArray));
System.out.println("Minimum Absolute Difference : "+minimum);
System.out.println("Pair Of Elements : ("+firstElement+", "+secondElement+")");
}
public static void main(String[] args)
{
minimumAbsoluteDifference(new int[] {5, 8, 4, 2, 9, 0});
System.out.println("==========================");
minimumAbsoluteDifference(new int[] {45, -89, 12, -62, 31, -57});
System.out.println("==========================");
minimumAbsoluteDifference(new int[] {5, -3, 7, -2});
}
}
Output :
Sorted Input Array : [0, 2, 4, 5, 8, 9]
Minimum Absolute Difference : 1
Pair Of Elements : (4, 5)
==========================
Sorted Input Array : [-89, -62, -57, 12, 31, 45]
Minimum Absolute Difference : 5
Pair Of Elements : (-62, -57)
==========================
Sorted Input Array : [-3, -2, 5, 7]
Minimum Absolute Difference : 1
Pair Of Elements : (-3, -2)
2. Without Sorting:
This method is less efficient than the above method. It’s time complexity is O(n2). In this method, we don’t sort the given array. We find the absolute difference between every possible pairs using brute-force method.
import java.util.Arrays;
public class JavaArrayProgram
{
private static void minimumAbsoluteDifference(int[] inputArray)
{
int minimum = Integer.MAX_VALUE;
int firstElement = inputArray[0];
int secondElement = inputArray[1];
for (int i = 0; i < inputArray.length-1; i++)
{
for (int j = i+1; j < inputArray.length; j++)
{
if(Math.abs(inputArray[i]-inputArray[j]) < minimum)
{
minimum = Math.abs(inputArray[i]-inputArray[j]);
firstElement = inputArray[i];
secondElement = inputArray[j];
}
}
}
System.out.println("Input Array : "+Arrays.toString(inputArray));
System.out.println("Minimum Absolute Difference : "+minimum);
System.out.println("Pair Of Elements : ("+firstElement+", "+secondElement+")");
}
public static void main(String[] args)
{
minimumAbsoluteDifference(new int[] {5, 8, 4, 2, 9, 0});
System.out.println("==========================");
minimumAbsoluteDifference(new int[] {45, -89, 12, -62, 31, -57});
System.out.println("==========================");
minimumAbsoluteDifference(new int[] {5, -3, 7, -2});
}
}
Output :
Input Array : [5, 8, 4, 2, 9, 0]
Minimum Absolute Difference : 1
Pair Of Elements : (5, 4)
==========================
Input Array : [45, -89, 12, -62, 31, -57]
Minimum Absolute Difference : 5
Pair Of Elements : (-62, -57)
==========================
Input Array : [5, -3, 7, -2]
Minimum Absolute Difference : 1
Pair Of Elements : (-3, -2)
Harshit Jain 