How do I find the minimum absolute difference between any two elements in an array?

Question

Here is my solution:

public static int minimumAbsoluteDifference(List<Integer> arr) {
   int absValues = 0;
   int maxNum = Integer.MAX_VALUE;
   Collections.sort(arr);
   for (int i = 0; i < arr.size() - 1; i++){
      absValues = Math.abs(arr.get(i) - arr.get(i + 1));
   }
   int absValuesDiff = Math.min(absValues, maxNum);
   return absValuesDiff;
}

I pass small test cases, but not ones with a larger data set.

Answer 1

The problem in your solution is that you're not checking all possible couples within the array of numbers.

With this for loop, for example:

for (int i = 0; i < arr.size() - 1; i++) {
    absValues = Math.abs(arr.get(i) - arr.get(i + 1));
}

And iterating over the simple array 1, 4, 6, 7, you would be checking the couples [1,4], [4,6] and [6,7], but you're still missing 1,7 and 4,7.

So step number one would be to iterate over the array per every number of the array (knowing that the order of the pairs doesn't matter [1,6] == [6,1] in this case, you will have to check 1 less number every iteration of the outer loop... here is an example of a correct for loop:

public static int minimumAbsoluteDifference(List<Integer> arr) {
    Collections.sort(arr);
    int minAbsoluteValue = Integer.MAX_VALUE;
    for(int i=0; i < arr.size() - 1; i++) {
        for(int j=i+1; j < arr.size(); j++)
           minAbsoluteValue = Math.min(Math.abs(arr.get(i) - arr.get(j)), minAbsoluteValue);
    }
    return minAbsoluteValue;
}

As you can see, another missing part in your solution is the tracking of the minimum value. You're checking the minimum value between the last iterated couple and the maxInteger value only once, while you have to that for every couple.

This might not be the most efficient solution...