Created
December 5, 2015 11:51
-
-
Save matchilling/155cfdd7e4b951ccd725 to your computer and use it in GitHub Desktop.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Example I/O
Explanation
The function findElementsByDistance() takes an integer
$k
and an array$a
as input values. Bydefinition the array
$a
is a sorted array (A[0] < A[1] < A[2] < ... < A[i]) and$k
defines the distancebetween 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$k
: the absolute value of the input variable k represents the distance between twopossible 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 asimple if-elseif-else statement in which it checks:
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.
4 - 0 === 20
isfalse
4 - 0 < 20
istrue
, so increase$j
15 - 0 === 20
isfalse
15 - 0 < 20
istrue
, so increase$j
23 - 0 === 20
isfalse
23 - 0 < 20
istrue
, so increase$i
23 - 3 === 20
, istrue
, add 3 and 23 to$results
and increase both pointers$j
&$i
25 - 4 === 20
isfalse
25 - 4 < 20
isfalse
, so increase$i
25 - 15 === 20
isfalse
25 - 15 < 20
istrue
, so increase$j
35 - 15 === 20
, istrue
, add values to$results
and increase both pointers$j
&$i
50 - 23 === 20
isfalse
50 - 23 < 20
isfalse
, so increase$i
50 - 25 === 20
isfalse
50 - 25 < 20
isfalse
, so increase$i
50 - 35 === 20
, istrue
, add 15 and 35 to$results
and increase both pointers$j
&$i
$i
is now not smaller than the number of elements in$a
[[3, 23], [15, 35]]