Given N integers, count the number of pairs of integers whose difference is K

I was given an array like this array(1,5,3,4,2);
Say k=2, I’m supposed to find out the count of pairs whose difference is 2. In this case it should return 3 because 5-3, 4-2, 3-1

Here’s what I have tried. It works fine I’m looping through the array twice O(n^2) complexity, I’m wondering if there is a better way to achieve this.

$arr = array(1,5,3,4,2); 
$k =2;
function find_pairs($arr, $k)
{
    $count = 0;
    for ($i=0 ; $i<= count($arr)-1 ; $i++)
    {
        for ($j=$i+1; $j <= count($arr)-1 ; $j++)
        {
            if ($arr[$i]-$arr[$j] == $k || $arr[$j]-$arr[$i]==$k)
            {
                $count++;
            }
        }
    }
    return $count;
}
echo find_pairs($arr, $k);

Thanks

Answer

Ofcourse, There are many ways:

Using Sorting:

Sort the array arr
Take two pointers, l and r, both pointing to 1st element
Take the difference arr[r] – arr[l]
If value diff is K, increment count and move both pointers to next element
if value diff > k, move l to next element
if value diff < k, move r to next element
return count

one with complexity of O(n) is :

1) Initialize count as 0.
2) Insert all distinct elements of arr[] in a hash map.  While inserting, 
   ignore an element if already present in the hash map.
3) Do following for each element arr[i].
   a) Look for arr[i] + k in the hash map, if found then increment count.
   b) Look for arr[i] - k in the hash map, if found then increment count.
   c) Remove arr[i] from hash table. 

Anyways you can refer to this link for more info.