# 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. – Dennis_E Oct 19 '17 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). – Gentian Kasa Oct 19 '17 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. – rolfl Oct 19 '17 at 6:27