Numbers, pairs, and a difference

Question

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 < sorted.length && highIndex < sorted.length) {
            long current = (long) sorted[highIndex] - sorted[lowIndex];
            if (current < difference) {
                highIndex++;
            } else if (current > 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;
                }
            }
        }

        return pairsFound;
    }

    private static int findEqual(int[] sorted, int index) {
        int matching = 1;
        while (index < sorted.length - 1 && sorted[index] == sorted[index + 1]) {
            index++;
            matching++;
        }
        return matching;
    }

}

Obligatory parametrized unit test, NumberPairsDiffTest.java:

@RunWith(Parameterized.class)
public class NumberPairsDiffTest {

    @Parameterized.Parameters
    public static Collection<Object[]> data() {
        return Arrays.asList(new Object[][]{
                {new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 4, 4},
                {new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 7, 8},
                {new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 0, 18},
                {new int[]{ 1 }, 0, 1},
                {new int[]{ 2, 2 }, 0, 3},
                {new int[]{ 3, 3, 3 }, 0, 6},
                {new int[]{ 4, 4, 4, 4 }, 0, 10},
                {new int[]{ 2, 2, 4 }, 0, 4},
                {new int[]{ 1, 4, 7, 11, 14, 17 }, -3, 4},
                {new int[]{ 1, 4, 7, 11, 14, 17 }, 5, 0},
                {new int[]{ Integer.MIN_VALUE, Integer.MAX_VALUE }, (long)(Integer.MAX_VALUE) * 2L + 1L, 1},
        });
    }

    @Parameterized.Parameter(value = 0)
    public int[] input;

    @Parameterized.Parameter(value = 1)
    public long diff;

    @Parameterized.Parameter(value = 2)
    public int expected;

    @Test
    public void test() {
        String string = String.format("Array %s with diff %d", Arrays.toString(input), diff);
        assertEquals(string, expected, NumberPairsDiff.pairsWithDifference(input, diff));
    }

}

Primary concerns

• Readable, understandable code?
• Missed edge-cases?
• Better approaches?

Answer 1

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 <= 1) {
            return 0;
        }
        
        if (difference == Long.MIN_VALUE) {
            return 0; 
        }
        
        if (difference < 0) {
            difference = -difference;
        }
        
        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++;

        if (difference == 0) {
            int pairsFound = 0;
            for (int i = 0; i < size; i++) {
                pairsFound += factorial(counts[i] - 1);
            }
            return pairsFound;
        }

        int left = 0;
        int right = 0;
        int pairsFound = 0;
        
        while (right < size) {
            long diff = (long)sorted[right] - (long)sorted[left];
            if (diff < difference) {
                right++;
            } else if (diff > 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 ;-)

Answer 2

First of all I am confused about the test cases for difference == 0. If I've only one input, i think the number of pairs is 0 (not 1) because I've no pair. If I've two equal values, i think the number of pairs is 1 (not 3)! And so on....

Apart from that, I tried to use a Map/Hashtable for counting the equal input values (so that there's no need for the findEqual-method.

public static int pairsWithDifference(final int[] input, final long difference) {
    Hashtable<Integer, Integer> equalCounter = new Hashtable<Integer, Integer>();
    for (int singleInput : input) {
        Integer counter = equalCounter.get(singleInput) == null ? 0 : equalCounter.get(singleInput);
        equalCounter.put(singleInput, counter + 1);
    }
    // equalCounter: Hashtable with input as key and amount of equal inputs as value

    // int[] sorted = Arrays.copyOf(input, input.length);
    Integer[] sorted = new Integer[0];
    sorted = equalCounter.keySet().toArray(sorted);
    Arrays.sort(sorted);

    int pairsFound = 0;

    int lowIndex = 0;
    int highIndex = 0;

    while (lowIndex < sorted.length && highIndex < sorted.length) {
        long current = (long) sorted[highIndex] - sorted[lowIndex];
        if (current < difference) {
            highIndex++;
        } else if (current > difference) {
            lowIndex++;
        } else {
            // Find out how many values are equal at `highIndex`
            int highMatching = equalCounter.get(sorted[highIndex]);
            int add;
            if (difference == 0) {
                // 1+2+3+4+5+...+n = 0.5x^2 + 0.5x
                add = (int) (0.5f * highMatching * highMatching + 0.5 * highMatching);
            } else {
                // Find out how many values are equal at `lowIndex`
                int lowMatching = equalCounter.get(sorted[lowIndex]);
                add = lowMatching * highMatching;
            }
            highIndex++;
            lowIndex++;
            pairsFound += add;
        }
    }

    return pairsFound;
}

Answer 3

Floating point police

As a proud member of the Floating Point Police™, I'm issuing you citation for unnecessary use of floating point here:

    int add = (int)(0.5f * highMatching * highMatching + 0.5 * highMatching);

First of all, the equation is wrong. The plus sign should be a minus. But second of all, you don't need floating point since \$n*(n-1)/2\$ is always integral. If you are afraid of integer overflow, you can cast to long:

    long add = (long) highMatching * (highMatching - 1) / 2;

Answer 4

{new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 4, 4} <-- That really confuses me but I don't see a better way for it – Ismael Miguel

Thought I'll provide some advice on this...

One can explore a Builder approach, something like:

private static class TestCaseBuilder {
    private final int[] values;
    private long diff;
    private long expected;

    private TestCaseBuilder(int... values) {
            this.values = values;
    }

    static TestCaseBuilder given(int... values) {
        return new TestCaseBuilder(values);
    }

    TestCaseBuilder andDifference(long diff) {
        this.diff = diff;
        return this;
    }

    TestCaseBuilder expect(long expected) {
        this.expected = expected;
        return this;
    }

    Object[] build() {
        return new Object[]{ values, diff, expected };
    }
}

It becomes (arguably) more readable:

// was
return Arrays.asList(new Object[][]{
        {new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 4, 4},
...

// now
return Arrays.asList(new Object[][]{
        TestCaseBuilder.given(4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42)
                        .andDifference(4).expect(4).build(),
...

Alternatively, drop the Builder in the name and treat this as the testing payload:

public class NumberPairsDiffTest {
    @Parameterized.Parameter
    public TestCase testCase;

    // ...

    @Test
    public void test() {
        String string = String.format("Array %s with diff %d", 
                            Arrays.toString(testCase.values), testCase.diff);
        assertEquals(string, testCase.expected, 
                NumberPairsDiff.pairsWithDifference(testCase.input, testCase.diff));
    }
}

Answer 5

My review goes along with most points provided by @rolfl namely about repeating pairs. Although IMO factorial does not suffice for repeating pairs, it's true that in the array [4, 4, 4] you only have the pair (4, 4) but I considered all the possible combinations to be valid pairs thus (4(0), 4(1)), (4(0), 4(2)) and (4(1), 4(2)) are different pairs.

But you can easily have your own approach on how to count those scenarios.

IMO the worst about your code is that you are mixing two different algorithms, the binary search, and the count of pairs. I suggest strongly to separate those.

public static int[] binarySearch(int[] list, int elem)
{
    return binarySearch(list, elem, 0, list.length - 1);
}

public static int[] binarySearch(int[] list, int elem, int left, int right)
{
    int idxFirst = -1;
    int auxRight = right;
    int auxLeft = -1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (list[mid] > elem)
        {
            right = mid - 1;
        }
        else if (list[mid] < elem)
        {
            left = mid + 1;
        }
        else
        {
            if (list[right] > elem)
            {
                auxRight = right + 1;
            }
            right = mid - 1;
            idxFirst = mid;
            auxLeft = auxLeft < 0 ? mid : auxLeft;
        }
    }
    int idxLast = binarySearchLast(list, elem, auxLeft, auxRight);
    return new int[]{idxFirst, idxLast};
}

public static int combinations(int elements, int length)
{
    return factorial(elements, elements - length + 1)/factorial(length, 2);
}

private static int factorial(int n, int stop){
  if(n<=stop){return n;}
  return n * factorial(n-1, stop);
}

private static int binarySearchLast(int[] list, int elem, int left, int right)
{
    int idxLast = -1;
    int mid = left + (right - left) / 2;
    while (left <= right && mid > -1)
    {
        if (list[mid] > elem)
        {
            right = mid - 1;
        }
        else if (list[mid] < elem)
        {
            left = mid + 1;
        }
        else
        {
            left = mid + 1;
            idxLast = mid;
        }
        mid = left + (right - left) / 2;
    }
    return idxLast;
}


public static int pairsWithDifference(int[] input, long difference) {
    if(input.length <= 1){
      return 0;
    }

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

    int pairsFound = 0;
    for(int i = 0 ; i < sorted.length; ++i){
        int[] interval = binarySearch(sorted, (int)(difference + sorted[i]));
        if(interval[0] > -1){

          boolean sumsTodifference = ((long)sorted[i] - sorted[interval[0]]) == difference || 
              ((long)sorted[interval[0]] - sorted[i]) == difference;

          if(sumsTodifference){
              if(sorted[interval[0]] == sorted[i]){
                //we are on a sequence with repeated numbers
                pairsFound += combinations(interval[1] - interval[0] + 1, 2);
                i = interval[1] + 1;
              }else{
                pairsFound += interval[1] - interval[0] + 1;
              }
          }
        }
    }

    return pairsFound;
}

Those are the tests according to what I would expect:

public static void main (String[] args) throws java.lang.Exception
{
    Object[][]  tests = new Object[][]{
            {new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 0l, 6},
            {new int[]{ 1 }, 0l, 0},
            {new int[]{ 2, 2 }, 0l, 1},
            {new int[]{ 3, 3, 3 }, 0l, 3},
            {new int[]{ 4, 4, 4, 4 }, 0l, 6},
            {new int[]{ 2, 2, 4 }, 0l, 1},
            {new int[]{ 1, 4, 7, 11, 14, 17 }, -3l, 4},
            {new int[]{ 1, 4, 7, 11, 14, 17 }, 5l, 0},
            {new int[]{ Integer.MIN_VALUE, Integer.MAX_VALUE }, (long)(Integer.MAX_VALUE) * 2L + 1L, 1},
    };
    for(Object[] test : tests){
        int pairs = pairsWithDifference((int[])test[0], (long)test[1]);
        System.out.println(pairs + "=" + (int)test[2]);
    }
}