Numbers, pairs, and a difference

Problem statement:

Write a function which returns the total number of combinations whose difference is k.

For example, 4 8 15 16 23 42 and the difference 7 has 2 pairs, 8, 15 and 16, 23.

I liked the Finding number of number pairs with given difference question so much (despite its brokenness) that not only did I review it, but I also decided to write up my own implementation of it (following the approach I described in my review). I was intrigued by this comment:

You need the handle the case of elements being equal too, though. That means an array with 2x duplicates such as 4 4 8 8 15 15 16 16 23 23 42 42 should return 4x the number of combinations as without duplicates. - JS1

When a pair is found, I count how many numbers are matching at lowIndex and highIndex respectively, and then calculating how many pairs there are.

NumberPairsDiff.java

``
public class NumberPairsDiff {

public static int pairsWithDifference(int[] input, long difference) {
int[] sorted = Arrays.copyOf(input, input.length);
Arrays.sort(sorted);

int pairsFound = 0;

int lowIndex = 0;
int highIndex = 0;

while (lowIndex difference) {
lowIndex++;
} else {
// Find out how many values are equal at highIndex
int highMatching = findEqual(sorted, highIndex);
highIndex += highMatching;

if (difference == 0) {
// 1+2+3+4+5+...+n = 0.5x^2 + 0.5x
int add = (int)(0.5f highMatching highMatching + 0.5 * highMatching);
pairsFound += add;
lowIndex += highMatching;
} else {
// Find out how many values are equal at lowIndex`
int lowMatching = findEqual(sorted, lowIndex);
lowIndex += lowMatching;
pairsFound += lowMatching * highMatching;
}
}

The basic algorithm you use is logical, and well presented. The general style is standard, and I see no issues there. I believe the algorithm can be changed slightly to make the comparison code simpler, but the performance will still be comparable.

I looked for edge cases I would have expected, specifically relating to large differences, but you appear to have covered that well. Unfortunately, your pair-counts for diff == 0 are all off. For example, your third test case:

{new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 0, 18},

should have a count of 6, and not 18. There are only 6 pairs with difference 0. The pair at index 0, and 1, is the same pair as index 1 and 0, so you can't double (or, for some reason triple) count them.

This also applies to cases like: {new int[]{ 1 }, 0, 1},.... you have an input array of just a single element... but you have 1 pair with diff 0? Really???

There is one small performance improvement related to how far you need to iterate in the loop - you have: while (lowIndex < sorted.length && highIndex < sorted.length) { but that can be just while (highIndex < sorted.length) { since lowIndex is always less than or equal to highIndex. This is particularly confusing if your input difference is negative.

For some reason, and I can't explain it, I prefer left and right for those variable names too... lowIndex seems not-quite-right, but I understand it anyway. Just a niggly thing.

Additionally, there are a few places where I would do things in a more Java-8 way. Let's deal with the smaller items first...
Small things

Consider this code:

int[] sorted = Arrays.copyOf(input, input.length);
Arrays.sort(sorted);

I would (now) use the following:

int[] sorted = IntStream.of(input).sorted().toArray();

As for negative difference input values, I would just handle that as an up-front special condition. The count of pairs with a negative difference will be the same as the count with a positive difference and the same magnitude. Just convert negative difference to positive, and handle the Long.MIN_VALUE special case.
Algorithm

I would alter the algorithm a little. I would have a simple scan of the data to count value duplicates, and store that count in a separate array. With that data structure, the search for duplicates later is much easier. Consider this:

if (input.length <= 1) {
        return 0;
    }
    
    int[] sorted = IntStream.of(input).sorted().toArray();
    
    // remove and count duplicate values
    int[] counts = new int[sorted.length];
    int size = 0;
    for (int i = 0; i < sorted.length; i++) {
        if (sorted[i] != sorted[size]) {
            sorted[++size] = sorted[i];
        }
        counts[size]++;
    }
    size++;

The above code ends up with a simpler data set to navigate. Unfortunatley, it makes the case where diff==0 a little more complicated... you need to use factorials for that, and not simple products. (Edit, I extracted that logic completely)....

Still, I put the whole method together as:

import java.util.stream.IntStream;

public class NumberPairsDiff {

    public static int pairsWithDifference(int[] input, long difference) {
        
        if (input.length  difference) {
                left++;
            } else {
                pairsFound += counts[left++] * counts[right++];
            }
        }
        return pairsFound;

    }

    private static int factorial(int n) {
        int f = n;
        while (--n > 1) {
            f *= n;
        }
        return f;
    }

}

The above function fails a bunch of your test cases because it produces the correct results ;-)

StackExchange Code Review Q#102086, answer score: 10