How to remove values using a blacklist array, then reduce the remaining values to eliminate gaps?

Question

This question is basically an extension of my previous question:

How to subtract value of array but still in position

I have an input array of arrays. The values in each subarray always consist of values starting from 0 and without any gaps, values are incremented by one. However, the values are not necessarily in order AND I need to preserve this order while executing my required logic.

Next I have a blacklist of values that I wish to remove from all subarrays. Any original subarray value that exists in the blacklist array must be removed.

Sample input array of arrays:

$arrays = [
    [0, 3, 10, 5, 6, 9, 2, 7, 1, 4, 8, 11],
    [0, 1, 2, 3],
    [0, 5, 2, 4, 3, 1],
    [0, 1, 3, 2]
];

Sample blacklist array:

$deletes = [3, 5];

My desired output is:

[
    [0, 8, 4, 7, 2, 5, 1, 3, 6, 9],
    [0, 1, 2],
    [0, 2, 3, 1],
    [0, 1, 2],
]

All remaining values greater than 3 are reduced by 1 and values greater than 5 are reduced by 2 since I deleted 2 numbers.

If all numbers in a given subarray are less than all of the numbers in the blacklist array, then no change is required for that subarray.

I have a coding attempt here https://3v4l.org/lX2MP, but I am stuck when returning their values. All array values were combining.

Answer 1

To delete numbers from array and to subtract a count from the current number in the original array with the number of numbers smaller than it in selectedDeletedNumbers, you can:

• Sort the selectedDeletedNumbers array.

• Iterate over the original array and use binary search to get the count of numbers smaller than the current number in the original array and subtract it later.

• If current number is present in selectedDeletedNumbers, then unset them.

• Apply the above operation on each individual subarray.

Snippet:

<?php

function subtract(&$arr,$selectedDeletedNumbers){ // pass by reference to edit the same copy of the array
    foreach($arr as $index => $val){
        $low = 0;$high = count($selectedDeletedNumbers) - 1;
        $equal_found = false;
        while($low <= $high){
            $mid = intval(($low + $high) / 2);
            if($selectedDeletedNumbers[$mid] > $val){
                $high = $mid - 1;
            }else if($selectedDeletedNumbers[$mid] < $val){
                $low = $mid + 1;
            }else{
                $equal_found = true;
                unset($arr[$index]); // if equal value, delete it as it your need
                break;
            }
        }
    
        if(!$equal_found){
            $arr[$index] -= $low; // delete the offset till where it is greater among your $selectedDeletedNumbers
        }
    }
}

$selectedDeletedNumbers = [3,5];
sort($selectedDeletedNumbers); // sort to be apply binary search later
$arr = [[0, 3, 10, 5, 6, 9, 2, 7, 1, 4, 8, 11], [0, 1], [0, 1], [0, 1]];

foreach($arr as &$val){ // pass by reference to edit the same copy of the array
    subtract($val,$selectedDeletedNumbers); 
}

print_r($arr);

Demo: https://3v4l.org/RMh5U

If you want to re-index the numbers sequentially, do an array_values() on each individual subarray in the end.

Answer 2

I am going to alter your 2nd, 3rd and 4th subarrays slightly to better demonstrate the behavior.

Drawing upon one of the techniques in my answer to your previous question, I am effectively only just wrapping the code logic in an additional loop array_map().

array_diff() is used to instantly destroy any values in the input array that match the deletes values. Then array_reduce() is use on the remaining values of the input array to iterate and reduce the integers any generated eliminate gaps.

Inside of array_reduce(), you will see $value > $item. This comparison will return true or false. When a boolean value is used as a number, true becomes 1 and false becomes 0. Basically, I am either subtracting 0 or 1 from $value depending on how each $deletes value compares to the given $value.

As a specific example, when processing 10, 10 is larger than 3, so it becomes 9, and 10 is larger than 5 so 9 becomes 8.

This is all done without needing to pre-sort the data.

Code: (Demo)

$arrays = [[0, 3, 10, 5, 6, 9, 2, 7, 1, 4, 8, 11], [0, 1, 2, 3], [0, 5, 2, 4, 3, 1], [0, 1, 3, 2]];
$deletes = [3, 5];

var_export(
    array_map(
        function($array) use ($deletes) {
            $result = [];
            foreach (array_diff($array, $deletes) as $value) {
                $result[] = array_reduce(
                    $deletes,
                    function ($carry, $item) use ($value) {
                        return $carry - ($value > $item);
                    },
                    $value
                );
            }
            return $result;
        },
        $arrays
    )
);

Here's an alternative that behaves the same way but doesn't rely on functional programming so much: (Demo)

foreach ($arrays as $index => $array) {
    $filtered = array_diff($array, $deletes);  // destroy blacked values
    foreach ($filtered as $value) {
        $originalValue = $value;
        foreach ($deletes as $delete) {
            $value -= $originalValue > $delete; // reduce to eliminate gaps
        }
        $result[$index][] = $value;
    }
}

var_export($result);

Output (for either snippet):

array (
  0 => 
  array (
    0 => 0,
    1 => 8,
    2 => 4,
    3 => 7,
    4 => 2,
    5 => 5,
    6 => 1,
    7 => 3,
    8 => 6,
    9 => 9,
  ),
  1 => 
  array (
    0 => 0,
    1 => 1,
    2 => 2,
  ),
  2 => 
  array (
    0 => 0,
    1 => 2,
    2 => 3,
    3 => 1,
  ),
  3 => 
  array (
    0 => 0,
    1 => 1,
    2 => 2,
  ),
)