Find elements in a sorted array $a with a specific distance $k iteratively and return the matching values or an empty array if no pair was found. The boolean value false is returned, if the array is not sorted.

findElementsByDistance.php

/**
 * Find elements in a sorted array $a with a specific distance $k iteratively and
 * return the matching values or an empty array if no pair was found. The boolean value
 * false is returned, if the array is not sorted.
 *
 * @param  integer  $k
 * @param  array    $a
 * @return mixed    (array|boolean)
 */
function findElementsByDistance($k, array $a)
{
    $results = array();
    $length  = count($a);
    $i = 0;
    $j = 1;

    while ($i < $length && $j < $length) {

        if (isset($a[$i + 1]) && $a[$i] > $a[$i + 1] || isset($a[$j + 1]) && $a[$j] > $a[$j + 1]) {
            return false;
        }

        if ($k === $a[$j] - $a[$i]) {
            $results[] = [
                $i => $a[$i],
                $j => $a[$j]
            ];
            $i++;
            $j++;
        } else if ($a[$j] - $a[$i] < $k) {
            $j ++;
        } else {
            $i ++;
        }
    }

    return $results;
}

Example I/O

print( findElementsByDistance(20, [0, 3, 4, 15, 23, 25, 35, 50]) );

// Output [ [3, 23], [15, 35] ]

Explanation

The function findElementsByDistance() takes an integer $k and an array $a as input values. By
definition the array $a is a sorted array (A[0] < A[1] < A[2] < ... < A[i]) and $k defines the distance
between one or more pairs of elements within the array we are looking for.

Temporary variables:

• $results: holds all pairs of elements which meets our criteria
• distance $k: the absolute value of the input variable k represents the distance between two
  possible values we are looking for
• length: the number of elements in array $a
• $i & $j: pointers which help us to iterated through the array,

After the initiation of all temporary variables the program runs through a while loop as long as $i and
$j are smaller than the length of the given array A. Within the while loop the program executes a
simple if-elseif-else statement in which it checks:

• if the array is sorted and
• whether the difference between two distinct values equals the distance we are looking for,
• or whether the difference between two distinct values is smaller than the distance,
• otherwise the difference between the compared values is greater

Now, in order to visualized the solution let's take an example and run it through the algorithm.
Assume $k is 20 and array A contains the following values: 0, 3, 4, 15, 23, 25, 35, 50.

1st iteration: The while loop will start computing the difference between 3 minus 0 ($a[$j] –
$a[$i]) which leads to 3. Hence 3 is not the difference (20 == 3 is false) we are looking for it will
skip the first if condition and will continue with the “else-if” statement. Hence 3 - 0 < 20 will return
boolean true, the program increases the pointer j by one and start the 2nd iteration.

• 2nd iteration
  • 4 - 0 === 20 is false
  • 4 - 0 < 20 is true, so increase $j
• 3rd iteration
  • 15 - 0 === 20 is false
  • 15 - 0 < 20 is true, so increase $j
• 4th iteration
  • 23 - 0 === 20 is false
  • 23 - 0 < 20 is true, so increase $i
• 5th iteration
  • 23 - 3 === 20, is true, add 3 and 23 to $results and increase both pointers $j & $i
• 6th iteration
  • 25 - 4 === 20 is false
  • 25 - 4 < 20 is false, so increase $i
• 7th iteration
  • 25 - 15 === 20 is false
  • 25 - 15 < 20 is true, so increase $j
• 8th iteration
  • 35 - 15 === 20, is true, add values to $results and increase both pointers $j & $i
• 9th iteration
  • 50 - 23 === 20 is false
  • 50 - 23 < 20 is false, so increase $i
• 10th iteration
  • 50 - 25 === 20 is false
  • 50 - 25 < 20 is false, so increase $i
• 11th iteration
  • 50 - 35 === 20, is true, add 15 and 35 to $results and increase both pointers $j &
    $i
• end of while loop, because $i is now not smaller than the number of elements in $a
• return results with [[3, 23], [15, 35]]