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

Basic Implementation

basic.py 
arr = [3, 5, 2, 5, 3, 8, 2]
count = {}
for value in arr:
    count[value] = count.get(value, 0) + 1
for value in arr:
    if count[value] == 1:
        print(value)
        break

Complexity

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

Implementation notes

  • Python uses a plain dict named count, with immutable int values as keys and integer frequencies as values. count.get(value, 0) + 1 performs a hash lookup with a default, then the assignment inserts or updates that entry.
  • The implementation is intentionally two pass: the first loop builds the full count table, and the second loop walks arr again so original list order, not dict insertion order, decides the first non-repeating value.
  • Hash collisions and table resizing are not visible for this small fixture; Python manages count while it is referenced and can reclaim it once unreferenced. The replay shows each count update, then scans until count[8] == 1 and prints 8.
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.