Counting pairs that have a given difference in Java

Question

You will be given an integer k and a list of integers. Count the number of distinct valid pair of integers (a,b) in the list for which a+k=b.

For example, the array [1,1,1,2] has two different valid pairs:(1,1) and (1,2). Note that the three possible instances od pair (1,1) count as a single valid pair, as do the three possible instances of the pair (1,2). if k=1, then this means we have total of one 1 valid pair which satisfies a+k=b=>1+1=2, the pair (1,2).

My code:

public class PairArrayStream {

    public static void main(String[] args) {
        int k =1;
        List<Integer> input = Arrays.asList(1,1,1,2);
        HashSet<HashSet> hs = new HashSet<HashSet>();
        IntStream.range(0,  input.size())
        .forEach(i -> IntStream.range(0,  input.size())
            .filter(j -> i != j && input.get(i) - input.get(j) == k)
            .forEach(j -> {                 
                 HashSet inner = new HashSet<>();
                 inner.add(input.get(j));
                 inner.add(input.get(i));
                 hs.add(inner);                 
            })
    );
        System.out.println("OutPut "+hs.size());
}

}

Without java 8 features::

int k =1;
  List<Integer> input = Arrays.asList(1,1,1,2);
  HashSet<HashSet> hs = new HashSet<HashSet>();    
   for(int i =0 ; i<numbers.size();i++){
       for(int j = i; j<numbers.size();j++){
           if(Math.abs(numbers.get(j)-numbers.get(i)) == k){
                HashSet inner = new HashSet<>();
                 inner.add(numbers.get(j));
                 inner.add(numbers.get(i));
                 hs.add(inner);
           }
       }
   }

Well, I am getting the correct output but 40% of the test cases gives me a timeout. Opinions and tactics are welcomed to make the code better and fast.

Answer 1

From a review of your code, I see that you loop over your input in a nested for loop. This is actually not required to solve the problem. Instead, create one hashset for every number in your numbers array, and another hashset for every number in numbers + k. Then we only have to check for intersections.

This should take your \$O(n^2)\$ algorithm and turn it into a nicer \$O(n)\$. Here's my suggested code (note that I included an inner class to store the pairs, but you could use builtins to solve it too:

private static class Pair {
    public int a;
    public int b;
    public Pair(int a, int b) {
        this.a = a;
        this.b = b;
    }
    public String toString() {
        return "("+a+","+b+")";
    }
}

public static List<Pair> getPairsFast(int k, List<Integer> numbers) {
    HashSet<Integer> hLow = new HashSet<>();
    HashSet<Integer> hHigh = new HashSet<>();
    List<Pair> ret = new ArrayList<>();
    for (int i : numbers) {
        hLow.add(i);
        hHigh.add(i+k);
    }
    for (int i : hHigh) {
        if (hLow.contains(i)) {
            ret.add(new Pair(i-k, i));
        }
    }
    return ret;
}

From some testing, it indeed seems to perform better the larger the input is, and it is >400 times faster for an input of size \$10^5\$.

Answer 2

I can't make comment on the java, but I do have a couple of comments on the algorithm.

You pose the problem as a+k=b, but you use i, j in your code. The logical naming paradigm would be to stick with a, b. You also don't use k, where is it?

To me, it looks like you have tried to overcomplicate things because you wanted to use the cool java functions. You start with an array, but you then turn it into an IntStream. You then loop through the IntStream. Why not just loop through the array?