Find the number of pairs in an array whose difference is K?

Question

So basically what I'm trying to do is

static int NumdiffExponential(int[] arr, int K)
{
    return (from i in arr
            from j in arr
            where (j - i) == K
            select 1).Count();
}

except in linear time, preferably with a single LINQ query and in a way that is compact, readable and micro-optimal. So what I came up with is the attempt

static int NumdiffLinear(int[] arr, int K)
{
    var counters = 
        arr
        .GroupBy(i => i)
        .ToDictionary(g => g.Key, g => g.Count());
    return 
        counters
        .Keys
        .Aggregate(
            0, 
            (total, i) => total + counters[i] * (counters.ContainsKey(K - i) ? counters[K - i] : 0)
        ); 
}

which keeps coming out as 0 and I can't figure out why.

Let me explain how I think it works. If we have arr={1,1,1,2,3,3,5} and K=2, then the counter is like

1->3, 2->1, 3->2, 5->1 

Let count = 0.

I take the key 1 and see that 1-K=-1 is not a key in counter and therefore count =0 still. Same with the key 2.

For the key 3 we have 3-K=1 which is a key in counter. There are 3 occurrences of the key 1 (i.e. counter[3]=1 and 2 occurrences of the key 2. Therefore count = 3*2 = 6 because of the pairs (1,3),(1,3),(1,3),(1,3),(1,3),(1,3),(1,3) which can be formed.

By the same logic as above, we add one more to count because of the pair (3,5). So the answer is count = 7.

Anything wrong with my algorithm or the implementation of it?

Answer 1

More readable and much more compact:

static int NumdiffLinear(int[] arr, int K)
{
    return arr.SelectMany(v => arr, (a, b) => new { a, b })
                .Where(s => s.b - s.a == K)
                .Count();
}

Here is a linear one with the same principle:

static int NumdiffLinear(int[] arr, int K)
{
    int n = 1;
    return arr.Select(value => new { value, index = n++ }) //Get number and index
                .SelectMany(indexValue => arr.Skip(indexValue.index), (a, b) => new { a = a.value, b }) //Project it with the next elements in the array
                .Where(s => s.a - s.b == K) //Do the math
                .Count();
}