exceeds execution time limit on pair difference challenge

Question

I recently had to do a code challenge where I was instructed that for a set of numbers, find the number of pairs whose difference was K. For example, given then numbers 1, 5, 3, 4, 2, and the difference K (2) there are 3 pairs: (5,3) (4,2) (3,1). I tried this challenge in PHP. My code passed the test, but was inefficient i guess because some of the test timed out. Can anyone tell me how I could have improved it? I'm bashing my head because I can't figure out how I could make it more efficient.

Here's my code

<?php
    // Open STDIN for reading
    $stdin = fopen('php://stdin', 'r');

    // Get the input
    while(!feof($stdin)) {
        $inputs[] = explode(' ', fgets($stdin));
    }
    fclose($handle);

    $k = $inputs[0][1];
    $values = array_map('intval', array_values($inputs[1]));

    // Sort in decending order
    rsort($values);

    // Given the difference, K, find a pair for $left within
    // $right whose difference is K
    function findPair($k, $left, $right){
        foreach($right as $n) {
            if($left - $n == $k)
                return $n;
            // If the difference is greater than $k, there is no pair
            if($left - $n > $k)
                return false;
        }

        return false;
    }

    $pairs = 0;

    while(count($values) > 1){ 
        $left = array_shift($values);
        $n = findPair($k, $left, $values);

        if($n !== false)
            $pairs++;
    }

    echo $pairs;
?>

Answer 1

Your code have O(n^2) complexity - and so it will be inefficient on large data sets. It's O(n^2) since you're looping through all array with foreach inside your function and calling it in while in external loop.

But you can easily do the stuff with O(n x log(N)):

function binSearch($array, $value, $from=null, $till=null)
{
   $from = isset($from)?$from:0;
   $till = isset($till)?$till:count($array)-1;
   if($till<$from)
   {
      return null;
   }
   $middle = (int)($from + ($till - $from)/2);
   if($array[$middle]>$value)
   {
      return binSearch($array, $value, $from, $middle-1);
   }
   if($array[$middle]<$value)
   {
      return binSearch($array, $value, $middle+1, $till);
   }
   return $middle;
}

$data = [1, 5, 3, 4, 2];
$k    = 2;

sort($data); //O(n x log(n))
$count = 0;

foreach($data as $value) //O(n)
{
   $count += null===binSearch($data, $value+$k)?0:1;//O(log(N))
}
var_dump($count);

-so, you will use standard sort() with O(n log(n)) complexity and then use binary search N times. Binary search has O(log(n)) complexity, so loop complexity will be also O(n log (n)). Therefore, whole code complexity will be O(n log(n)) + O(n log(n)) = O(n log(n)).

Note: standard PHP's in_array() has O(N) complexity, so using it will produce O(N^2) complexity estimation for loop, and, therefore, O(N^2) code complexity.

Note: sorting via sort() will produce quick sorting. This algorithm has O(n log(n)) average complexity, it's worst case is O(N^2) - so there may be cases of data sets, for which code above may be also inefficient. You may look into other sorting algorithms. For example, if your problem is time limit, you may try merge sort - it will be extremely faster (but it will take additional space).

Note: If we're speaking about time complexity and space complexity does not matter, it's just simple hash-map that can be used. In PHP it's just array:

$array = [1, 5, 3, 4, 2];
$k = 2;

$count = 0;
$map   = [];

foreach ($array as $number) //O(n) time
{
   $map[$number] = $number;
}
foreach($map as $key=>$nevermind) //O(n) time
{
   //O(1) if there are no duplicates, very close to O(1) otherwise
   $count += array_key_exists($key+$k, $map); 
}

var_dump($count);

-that will result in O(n) time complexity and O(2n)=O(n) space complexity.