# Find all pairs in an array whose absolute difference equals x

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.

• Sorting will work just fine if you just store the original index with the value. You can also use a Hashtable for an $O(n)$ algorithm. But both these methods require additional $O(n)$ space. Oct 19, 2017 at 10:54
• If you transform the input array in a dictionary where the key is the item and the value is a list containing the indices of the item in the original array the complexity goes between $\Omega(n)$ (in case there is little repetition of the items) and $O(n^2)$ (in case there's a lot of repetition of the items). Oct 19, 2017 at 11:35

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))

• I agree that sorting is a good option to reduce the pairing computation, but consider three things: 1. your algorithm is still $O(n^2)$ because you nested-loop through the data (do a binary-search instead for an exact mate); 2. no need to do absolutes on the sorted-value checks; 3. part of the problem is to report the index of the values in the unsorted array, not just the values... so you need to keep track of both. Oct 19, 2017 at 6:27