Remove array elements that are less than X

Question

I have arrays:

$arr1 = array(5, 3, 9, 11, 6, 15);
$arr2 = array(11, 20, 1, 3, 8);

Now I need to loop through $arr1 and find the largest number that is less than X:

foreach($arr1 as $x) {
   //need element that is MAX in $arr2 but is less than $x
}

so for example for the first run when $x = 5, maximum in $arr2 is 3 that is less than 5.

Is it possible to do this without having nested loop? I do not want to loop through $arr2. I tried using array_filter but didnt really work. Maybe I used it wrong.

This is what I tried with array_filter:

$results = array();
foreach($arr1 as $x) {
   $max = max(array_filter($arr2, function ($x) { return $x < $y; }));

   $results[$x] = $max;
}

The result should be this:

5  => 3, 
3  => 1, 
9  => 8, 
11 => 8, 
6  => 3, 
15 => 11

Answer 1

The problem is with the use of the lambda - PHP does not automatically capture variables in the enclosing scope. (The official Anonymous Functions is a bit sparse on the topic, so see In PHP 5.3.0, what is the function "use" identifier? as well.)

Compare the original, which returns an empty array as it is effectively $x < undefined

$arr2 = array(11, 20, 1, 3, 8);
$y = 5;
var_dump(array_filter($arr2, function ($x) { return $x < $y; }));

with the following that employs the use syntax to bind the variable in the function

$arr2 = array(11, 20, 1, 3, 8);
$y = 5;
var_dump(array_filter($arr2, function ($x) use ($y) { return $x < $y; }));

(Also, in the original code there was no $y variable at all, whoops!)

Answer 2

Here's a method that uses array_map() to return the values that are lower than your maximum variable, then uses max() to return the highest (as in your example).

In this example I've used $var as a variable by reference (the &), so that it can be used by the get_highest() callback function which is accessing it as a global variable.

function get_highest($x) {
    global $var;
    return $x < $var ? $x : 0;
}

$results = array();    
foreach($arr1 as &$var) {
    $results[$var] = max(array_map('get_highest', $arr2));
}

Without using global variables

You can modify this if you don't want to use global variables by passing in an array of parameters to array_map(). It's a little strange the way it works, because the parameter array needs to be the same length as the original array, so I've used array_fill() to fill it up to the required length with the current value, so the callback function can use it to compare:

function get_highest($x, $y) {
    return $x < $y ? $x : 0;
}

$results = array();    
foreach($arr1 as $var) {
    $max = array_fill(0, count($arr2), $var);
    $results[$var] = max(array_map('get_highest', $arr2, $max));
}

Answer 3

Any solution that reuses/resets arr2 will be of quadratic complexity, meaning that if you have an arr1 of size N and an arr2 of size M, you'll be doing around N*M operations.

Plus function calls and parameter passing in case of lambda functions.

A better strategy if N and M are very large is to sort both arrays (complexity is N log N + M log M), then use the same strategy as merge sort to loop through the arrays, saving their state. This will execute in at most N+M operations instead of N*M, making the overall complexity linearithmic.

The lambda solution is easier to understand, more robust and simpler to maintain, so unless there's a pressing reason (N and M in the tens of thousands), it is to be preferred. You are trading speed for ease of maintenance; but it is normally a sweet deal.

First you sort both arrays with PHP's array sort functions, and get

$arr1 = array(3, 5, 6, 9, 11, 15);
$arr2 = array(1, 3, 8, 11, 20);

$map = array();

$n = count($arr1);
$m = count($arr2);

for ($i = 0, $j = 0, $y = false; $i < $n;) {
    if ($j == $m) {
        $map[$arr1[$i++]] = $y;
    } else {
        if ($arr1[$i] <= $arr2[$j]) {
            $map[$arr1[$i++]] = $y;
        } else {
            $y = $arr2[$j++];
        }
    }
}