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.

Basic Implementation

basic.ts 
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;
  }
}

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.
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.