2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Dennis_E Oct 19 '17 at 10:54
  • \$\begingroup\$ 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). \$\endgroup\$ – Gentian Kasa Oct 19 '17 at 11:35
1
\$\begingroup\$

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])
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – rolfl Oct 19 '17 at 6:27
  • \$\begingroup\$ As mentioned you sort in ascending order first. The point @pellucidcoder is trying to make is that you can break your inner loop as soon as the difference of the numbers at current indices is more than X, as all numbers after that will always yield a difference more than X. Theoretically it stays O(n2) but it will sure improve perf. \$\endgroup\$ – Gautam Oct 19 '17 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.