Find all pairs in an array whose absolute difference equals x

Question

I have an array A of integers with n values and an integer x. I need to find all the pairs in that array whose absolute difference is equal to x.

For example, take A = {13, 1,-8, 21, 0, 9,-54, 17, 31, 81,-46} and x = 8, my algorithm should print this:

0 & 3 with values 13 & 21
1 & 5 with values 1 & 9
2 & 4 with values -8 & 0
5 & 7 with values 9 & 17
6 & 10 with values -54 & -46

I worked out a solution, however, it is \$O(n^2)\$:

for (int i = 0 ; i < A.length; i ++)
    {
        for (int j = i; j < A.length; j++)
        {
          if (abs(A[i]-A[j]) == x)
             System.out.println("Indices " + i + " & " + j + " with values " + A[i] + " & "+ A[j]);
        }      
    }

1. Without sorting first, is there any way to optimize this code to be faster? I know \$O(n^2)\$ isn't great but I can't think of a better way of doing it (without sorting first).

2. For my algorithm, the best case Omega is also \$Ω(n^2)\$, correct? I need to compare every value in any case.

Answer 1

I don't have the rep to comment, and I know you said without sorting first, but if you are already at worst case performance of O(n^2), and sorting in theory is O(nlogn), why not then sort if it wont hurt your big-o performance?

i.e.

A.sortAscending() // however done in java. in theory is O(nlogn)

int j = 0;
for (int i = j; i < A.len; i++) {
    while (j < A.len && (abs(A[i] - A[j++]) < x))
        ; // do nothing

    // so now we are guarenteed absdiff(arr[i], arr[j]) <= x.
    // as soon as it != x we can move on because as the array is sorted
    // the difference will only increase, thus not equaling x again
    while (j < A.len && (abs(A[i] - A[j++]) == x))
        resultArray.add((arr[i], arr[j])
}