PHP: Equal Needle Segregation. Given an array containing Xs and Ys, find they key index in which the number of Xs on the left is equal to the number of Ys on right, where X is some arbitrary needle and Y is any element that is not X. The key position is inclusive of Xs.

equal_segregation.php

<?php

/**
 * Equal needle segregation
 * Given an zero-indexed array of values
 * Find the index where there is a equal number of X on the left hand side
 * To an equal number of Y on the right hand side.
 * X is the an arbitrary search needle.
 * Y is anything that is not the arbitrary search needle.
 * Example: [1, 2, 2, 3, 4];  X = 2
 * The answer is 2.
 * 2 is the index at which there is an equal number of Xs on the left to a equal number of Ys on the right.
 * There is 2 Xs [2, 2] and 2 Ys [3, 4].
 * The below function is somewhat O(2n) with 2 passes.
 * It uses a graph intersection method, by graphing the Xs as a positive incremental graph and Ys as a negative incremental graph. The graphs are just zero-indexed array, where the 0th index is the first increment/decrement of each respective graph.
 * We then push up the Ys by the apex of the Y graph, which makes both graphs positive.
 * We find the key at which the 2 graphs now intersect, every intersection is an index where there is an equal number of Xs on the left to an equal number Ys on the right.
 * This function just returns the first key it finds, however it could easily return an array of all the keys as well.
 *
 *  Example graphs given: [3, 5, 5, 5, 5, 1, 1, 4]; X = 5
 *     
 *     \   -- X
 *      --+
 *       / \
 *      /   \ Y
 *     -     
 *      012345
 *      
 *  2 is the correct index!
 *  
 */

function equal_opposites ($elements, $search) {

    $key = -1;

    $identified = [];
    $unidentified = [];

    $identified_coordinate = 0;
    $unidentified_coordinate = 0;

    foreach ($elements as $value) {

        if ($value == $search) {

            // if identified, then increment the identified value, but keep the unidentified value
            $identified_coordinate += 1;

            $identified[] = $identified_coordinate;
            $unidentified[] = $unidentified_coordinate;

        } else {

            // if unidentified, then decrement the unidentified value, but keep the identified value

            $unidentified_coordinate -= 1;

            $identified[] = $identified_coordinate;
            $unidentified[] = $unidentified_coordinate;

        }

    }

    // the unidentified apex is the last unidentified coordinate
    $unidentified_apex = -1 * ($unidentified_coordinate);

    // find the points of interception, by pushing up the unidentified graph by the unidentified apex
    $length = count($identified);
    for ($i = 0; $i < $length; $i++) {
        
        if ($identified[$i] == ($unidentified[$i] + $unidentified_apex)) {
            $key = $i;
            break;
        }

    }

    return $key;

}

$elements = [3, 5, 5, 5, 5, 1, 1, 4];
$equal_key_position = equal_opposites($elements, 5);