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 Perl DSA implementation can be compared directly with the rest of the DSA track.

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.

Basic Implementation

basic.pl
Replay: real traced execution (multi-file project)
use strict;
use warnings;

my @arr = (3, 5, 2, 5, 3, 8, 2);
my %count;
for my $value (@arr) {
    $count{$value} += 1;
}
for my $value (@arr) {
    if ($count{$value} == 1) {
        print "$value\n";
        last;
    }
}

  1. arr ← [3, 5, 2, 5, 3, 8, 2]

    1use strict;2use warnings;
    values this step[3, 5, 2, 5, 3, 8, 2]arr

  2. count ← {}

    4my @arr = (3, 5, 2, 5, 3, 8, 2);5my %count;6for my $value (@arr) {
    values this step{}count

  3. count ← {3: 1}

    4my @arr = (3, 5, 2, 5, 3, 8, 2);5my %count;6for my $value (@arr) {
    values this step{} → {3: 1}count3value

  4. count ← {3: 1, 5: 1}

    4my @arr = (3, 5, 2, 5, 3, 8, 2);5my %count;6for my $value (@arr) {
    values this step{3: 1} → {3: 1, 5: 1}count5value

  5. count ← {3: 1, 5: 1, 2: 1}

    4my @arr = (3, 5, 2, 5, 3, 8, 2);5my %count;6for my $value (@arr) {
    values this step{3: 1, 5: 1} → {3: 1, 5: 1, 2: 1}count2value

  6. count ← {3: 1, 5: 2, 2: 1}

    4my @arr = (3, 5, 2, 5, 3, 8, 2);5my %count;6for my $value (@arr) {
    values this step{3: 1, 5: 1, 2: 1} → {3: 1, 5: 2, 2: 1}count5value

  7. count ← {3: 2, 5: 2, 2: 1}

    4my @arr = (3, 5, 2, 5, 3, 8, 2);5my %count;6for my $value (@arr) {
    values this step{3: 1, 5: 2, 2: 1} → {3: 2, 5: 2, 2: 1}count3value

  8. count ← {3: 2, 5: 2, 2: 1, 8: 1}

    4my @arr = (3, 5, 2, 5, 3, 8, 2);5my %count;6for my $value (@arr) {
    values this step{3: 2, 5: 2, 2: 1} → {3: 2, 5: 2, 2: 1, 8: 1}count8value

  9. count ← {3: 2, 5: 2, 2: 2, 8: 1}

    4my @arr = (3, 5, 2, 5, 3, 8, 2);5my %count;6for my $value (@arr) {
    values this step{3: 2, 5: 2, 2: 1, 8: 1} → {3: 2, 5: 2, 2: 2, 8: 1}count2value

  10. i ← 0, value ← 3, count[value] ← 2, found ← no

    1use strict;2use warnings;
    values this step0i3value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  11. i ← 1, value ← 5, count[value] ← 2, found ← no

    1use strict;2use warnings;
    values this step1i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  12. i ← 2, value ← 2, count[value] ← 2, found ← no

    1use strict;2use warnings;
    values this step2i2value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  13. i ← 3, value ← 5, count[value] ← 2, found ← no

    1use strict;2use warnings;
    values this step3i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  14. i ← 4, value ← 3, count[value] ← 2, found ← no

    1use strict;2use warnings;
    values this step4i3value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

  15. i ← 5, value ← 8, count[value] ← 1, found ← yes, result ← 8

    1use strict;2use warnings;
    values this step5i8value1count[value]yesfound8result{3: 2, 5: 2, 2: 2, 8: 1}count

  16. stdout ← 8

    10if ($count{$value} == 1) {11    print "$value\n";12    last;
    values this step8stdout8result

Complexity

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

Implementation notes

  • The checked input is numeric, not characters: my @arr = (3, 5, 2, 5, 3, 8, 2).
  • my %count declares the Perl hash table with the % sigil.
  • The first pass is for my $value (@arr), so values are counted in input order.
  • Count updates use $count{$value} += 1; the first write creates that hash entry, then later writes increment the stored number.
  • Perl hash keys are strings internally, but numeric keys like 3, 5, 2, and 8 are looked up consistently through $count{$value}.
  • The count trace starts at {}, then records {3: 1}, {3: 1, 5: 1}, and {3: 1, 5: 1, 2: 1}.
  • Repeated values update the same hash entries: the final count table is {3: 2, 5: 2, 2: 2, 8: 1}.
  • The second pass also uses for my $value (@arr), so the first-non-repeating decision follows the original array order, not hash iteration order.
  • The condition is numeric: if ($count{$value} == 1).
  • The trace checks 3, 5, 2, 5, and 3; each has frequency 2, so no value is printed yet.
  • At array index 5, value 8 has frequency 1, so the code prints it and last stops the loop.
  • print "$value\n" interpolates the found scalar and outputs 8.