Hash Tables

First Non-Repeating Value

Find the first input value whose final frequency is one.

Algorithm

Canonical input [3, 5, 2, 5, 3, 8, 2] prints 8. The replay uses the same input in every language, so this PHP DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.php 
<?php
$arr = [3, 5, 2, 5, 3, 8, 2];
$count = [];
foreach ($arr as $value) {
    $count[$value] = ($count[$value] ?? 0) + 1;
}
foreach ($arr as $value) {
    if ($count[$value] === 1) {
        echo $value . PHP_EOL;
        break;
    }
}
?>

Complexity

  • Time: O(n) average
  • Space: O(k) for k distinct values

Implementation notes

  • The checked PHP source uses the numeric input array $arr = [3, 5, 2, 5, 3, 8, 2], not a string scan.
  • $count = [] is a PHP associative array used as the frequency table.
  • The first foreach ($arr as $value) walks values in input order and updates counts with $count[$value] = ($count[$value] ?? 0) + 1.
  • The null-coalescing read treats a missing key as 0 before the increment.
  • The trace grows the table as {3: 1}, {3: 1, 5: 1}, {3: 1, 5: 1, 2: 1}, then finishes at {3: 2, 5: 2, 2: 2, 8: 1}.
  • The second foreach scans $arr again instead of iterating the count table, so the result follows original input order.
  • The second pass rejects arr[0]=3, arr[1]=5, arr[2]=2, arr[3]=5, and arr[4]=3 because each has count 2.
  • At arr[5], $value is 8 and $count[$value] === 1, so the code prints 8 and breaks before scanning the final 2.
  • echo $value . PHP_EOL; is the only output path in the checked run.
two-pass lookup The first pass builds a frequency table. The second pass keeps the original order and stops at the first value with frequency one.