Given n numbers , n is very large. Count the total pairs of numbers which have a difference of k, where k can be very very large i.e. k>n . The solution should have as low of a computational time complexity as possible.

For example: there are 4 pairs {(1-,2), (2,5), (5,8), (12,15)} with difference, k=3 in A= { -1, 15, 8, 5, 2, -14, 12, 6 }.

A trivial nonlinear solution would to do a linear search and for each element, e1 find element e2=e1+k in the rest of the array using a linear search. This is O(n^2) solution. But we could do better.

O(n) time and O(n) space solution
1. Keep a hash table(HashSet would suffice) to keep the elements already seen while passing through array once.
2. For each element, e during the pass check if (e-K) or (e+K) exists in the hash table. If exists then increment a count.
3. Add the scanned element in the hash table.

public static int diffPairs(final int[] A, final int K) {
    final HashSet<Integer> hs = new HashSet<Integer>();
    int count = 0;

    for (int i = 0; i < A.length; i++) {
        if (hs.contains(A[i] - K)) {
            count++;
        }
        if (hs.contains(A[i] + K)) {
            count++;
        }

        hs.add(A[i]);
    }
    return count;
}

O(nlgk) time O(1) space solution
If we don’t have the space then there is another solution with O(1) space and O(nlgk) time. Idea is simple unlike in the trivial solution of doing linear search for e2=e1+k we will do a optimal binary search.

1. Sort the array , O(nlgn)
2. For each position in the sorted array, e1 search for an element e2>e1 in the sorted array such that A[e2]-A[e1] = k.

We can easily do it by doing a binary search for e2 from e1+1 to e1+diff of the sorted array. Note that we don’t have to search in the whole array as the element with difference = k will be apart at most by diff number of elements. Thus each search will be only O(logK). So for the whole scan time is O(nlgk). The overall complexity is O(nlgn)+O(nlgk). If k>n then time complexity of this algorithm is O(nlgk) wit O(1) space.

private static int binarySearch(final int[] A, int l, int r, final int key) {
    int m = -1;

    while (l <= r) {
        m = (l + r) / 2;

        if (A[m] == key) {
            return m;
        } else if (key < A[m]) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    return -1;
}

public static int diffPairs2(final int[] A, final int diff) {
    Arrays.sort(A);
    int count = 0;
    int matchKey = 0;
    int matchIndex = -1;

    for (int i = 0; i < A.length; i++) {
        // if we are in e1=A[i] and searching for a match=e2, e2>e1 such that e2-e1= diff then e2=e1+diff
        // So, potential match to search in the rest of the sorted array is match = A[i] + diff; We will do a binary
        // search. Also note that the math should be at most |diff| element away to right of the current position i
        matchKey = A[i] + diff;
        matchIndex = binarySearch(A, Math.min(i + 1, A.length - 1), Math.min(i + diff, A.length - 1), matchKey);
        count += (matchIndex != -1) ? 1 : 0;
    }

    return count;
}

Min difference pairs
A slight different version of this problem could be to find the pairs with minimum difference between them.

For example, in A=[-1, 15, 8, 5, 2, -14, 6, 7] min diff pairs are={(5,6), (6,7), (7,8)}.

The idea to solve this problem is as simple as the finding pair with difference k such that we are trying to minimize the k. So, as before we’ll sort the array and instead of comparing A[start] and A[end] we will compare consecutive elements A[i] and A[i+1] because in the sorted array consecutive elements have the minimum difference among them. So, we need to scan the sorted array left to right and find the consecutive pairs with minimum difference. Below is the O(nlgn) time code with O(1) space.

public static List<String> minDiffPairs(final int[] A) {
    ArrayList<String> pairs = new ArrayList<String>();
    int minDiff = Integer.MAX_VALUE;

    Arrays.sort(A);
    for (int i = 0; i < A.length - 1; i++) {
        if (Math.abs(A[i + 1] - A[i]) < minDiff) {
            pairs = new ArrayList<String>();
            pairs.add("(" + A[i] + "," + A[i + 1] + ")");
            minDiff = Math.abs(A[i + 1] - A[i]);
        } else if (Math.abs(A[i + 1] - A[i]) == minDiff) {
            pairs.add("(" + A[i] + "," + A[i + 1] + ")");
        }
    }

    return pairs;
}