Unsorted array - Getting index from next higher value | Complexity O(n), PHP

Question

I search a PHP algorithmus of complexity O(n). I have an array out of integer and I want for every element the index number of the nearest bigger value than this or -1 if it does not exist.
Note: Every value is unique.

Example:

$arr = [7, 3, 5, 4];
$result = [-1, 3, 0, 2];

Explanation:

• 7 has no bigger value => -1
• 3 next bigger value 4 => 3
• 5 next bigger value 7 => 0
• 4 next bigger value 5 => 2

Solution which works fine but it hat O(n²):

function follows ($arr, $index) {
    $filter = array_filter($arr, function($el) use ($arr, $index) { return $el > $arr[$index]; });
    if (count($filter)===0)
        return -1;
    else
        return array_search(min($filter), $arr);
}

$res = [];
for ($i=0; $i<count($arr); $i++) {
    $res[] = follows($arr,$i);
}
var_dump($res); // => [-1, 3, 0, 2]

Solution with O(n) searched

I supposed to use asort (in example: [3, 4, 5, 7]), so the values are sorted and I can get the original-index of the next element there.

This is part of an idea for it:

$arr = [ 7, 3, 5, 4];
asort($arr);
for($i=0; $i<count($arr); $i++) {
    echo 'For: ' . $i . ': ' . $arr[$i].'<br>';
}

echo "<br>";

foreach ($arr as $key => $val) {
    echo 'ForEach; ' . $key . ': ' . $val .'<br>';
}

echo '<br><br>' . $arr[2];

After the sorting with asort the indexes are the same as you can see with the for-loop but within the forEach-loop they are sorted new but the indexes are still same.
Idea: Take the index from the for-loop get the corresponding index of the forEach-loop increment it by 1 and get the original-index.
Example: Index 1 in my array has value 3 and in the for-loop still an index of 1 but in the forEach-loop an index of 0. Getting there the next element (index 1) with value 4 has an original-index of 3.

The last step is easy. Can anybody help to get the missing link from index of for to index of forEach without find?

Answer 1

Here's a version that doesn't flip the array so can work with any type of array data. It uses a single loop and an asort so is O(n*log(n)). Once the data is sorted, the key function is used to determine the key of the next larger value in a loop; when the loop finishes the final "next" value is set to -1 (since there is no larger value). At this point the output has the correct key/value pairs but not in numeric order (this may be sufficient for your needs):

$arr = [7, 3, 5, 4];
asort($arr);
$temp = [];
$count = 1;
$key = key($arr);
while (next($arr) !== false) {
    $temp[$key] = key($arr);
    $key = key($arr);
    $count++;
}
$temp[$key] = -1;
print_r($temp);

Output:

Array
(
    [1] => 3
    [3] => 2
    [2] => 0
    [0] => -1
)

If you need the keys sorted (for example, if you want the entries to be in order when you use a foreach loop), you can use another loop, taking advantage of the $count variable generated in the above code, to copy the values into a new, ordered array:

$result = [];
for ($i = 0; $i < $count; $i++) {
    $result[] = $temp[$i];
}
print_r($result);

Output:

Array
(
    [0] => -1
    [1] => 3
    [2] => 0
    [3] => 2
)

If you don't need this, you can remove the computation of $count from the first code block.

Demo on 3v4l.org