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

Basic Implementation

basic.js 
const arr = [3, 5, 2, 5, 3, 8, 2];
const count = new Map();
for (const value of arr) {
  count.set(value, (count.get(value) ?? 0) + 1);
}
for (const value of arr) {
  if (count.get(value) === 1) {
    console.log(value);
    break;
  }
}

Complexity

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

Implementation notes

  • JavaScript stores the input as a const Array of Number values, not a string. Both for...of loops visit values in array order, so the second pass preserves the original first-occurrence order.
  • Counts live in a real Map. The first pass updates each numeric key with count.set(value, (count.get(value) ?? 0) + 1), using 0 for a missing key and storing counts as Number values.
  • Map compares these finite numeric keys by SameValueZero semantics, which behaves like ordinary numeric equality here. Insertion order is stable for the replayed table display, but the lookup uses keys directly rather than iterating the map.
  • The replayed count table grows from {} to {3: 1}, {3: 1, 5: 1}, {3: 1, 5: 1, 2: 1}, and finally {3: 2, 5: 2, 2: 2, 8: 1}. The second pass rejects 3, 5, 2, 5, and 3 with count 2, then finds 8 at count 1.
  • console.log(value) prints the numeric result 8 and breaks. The lesson-visible heap allocation is the input array plus the Map; the scan itself only updates scalar bindings.
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.