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.

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.js
Replay: real traced execution (multi-file project)
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;
  }
}

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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();
    values this step[3, 5, 2, 5, 3, 8, 2]arr

  2. count ← {}

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();3for (const value of arr) {
    values this step{}count

  3. count ← {3: 1}

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();3for (const value of arr) {
    values this step{} → {3: 1}count3value

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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();3for (const value of arr) {
    values this step{3: 1} → {3: 1, 5: 1}count5value

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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();3for (const value of arr) {
    values this step{3: 1, 5: 1} → {3: 1, 5: 1, 2: 1}count2value

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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();3for (const value of 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}

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();3for (const value of 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}

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();3for (const value of 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}

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();3for (const value of 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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();
    values this step0i3value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();
    values this step1i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();
    values this step2i2value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();
    values this step3i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();
    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

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();
    values this step5i8value1count[value]yesfound8result{3: 2, 5: 2, 2: 2, 8: 1}count

  16. stdout ← 8

    1const arr = [3, 5, 2, 5, 3, 8, 2];2const count = new Map();
    values this step8stdout8result

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.