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 TypeScript 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.ts
Replay: real traced execution (multi-file project)
const arr: number[] = [3, 5, 2, 5, 3, 8, 2];
const count = new Map<number, number>();
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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();
    values this step[3, 5, 2, 5, 3, 8, 2]arr

  2. count ← {}

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

  3. count ← {3: 1}

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

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

    1const arr: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();
    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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();
    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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();
    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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();
    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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();
    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: number[] = [3, 5, 2, 5, 3, 8, 2];2const count = new Map<number, number>();
    values this step5i8value1count[value]yesfound8result{3: 2, 5: 2, 2: 2, 8: 1}count

  16. stdout ← 8

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

Complexity

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

Implementation notes

  • TypeScript declares the input as const arr: number[]; this checked lesson iterates numeric values, not string characters.
  • Counts are stored in new Map<number, number>(), so both keys and frequency values are typed as number.
  • The first pass uses for (const value of arr) and writes count.set(value, (count.get(value) ?? 0) + 1). The nullish coalescing default handles the undefined result for a value not seen before.
  • The second pass scans the same array order and checks whether count.get(value) is 1. Every scanned value was inserted during the first pass, so the replay does not observe an undefined count lookup in this phase.
  • The trace grows the table from {} to {3: 1}, {3: 1, 5: 1}, {3: 1, 5: 1, 2: 1}, and finally {3: 2, 5: 2, 2: 2, 8: 1}. It rejects counts of 2 until value 8 has count 1.
  • console.log(value) prints 8 and breaks. Visible allocation is the input array and the Map; mutation is limited to count.set.