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 C 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.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

int main(void) {
    int arr[] = {3, 5, 2, 5, 3, 8, 2};
    int count[10] = {0};
    int n = 7;
    for (int i = 0; i < n; i++) {
        count[arr[i]] += 1;
    }
    for (int i = 0; i < n; i++) {
        if (count[arr[i]] == 1) {
            printf("%d\n", arr[i]);
            break;
        }
    }
}

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

    1#include <stdio.h>
    values this step[3, 5, 2, 5, 3, 8, 2]arr

  2. count ← {}

    4int arr[] = {3, 5, 2, 5, 3, 8, 2};5int count[10] = {0};6int n = 7;
    values this step{}count

  3. count ← {3: 1}

    4int arr[] = {3, 5, 2, 5, 3, 8, 2};5int count[10] = {0};6int n = 7;
    values this step{} → {3: 1}count3value

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

    4int arr[] = {3, 5, 2, 5, 3, 8, 2};5int count[10] = {0};6int n = 7;
    values this step{3: 1} → {3: 1, 5: 1}count5value

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

    4int arr[] = {3, 5, 2, 5, 3, 8, 2};5int count[10] = {0};6int n = 7;
    values this step{3: 1, 5: 1} → {3: 1, 5: 1, 2: 1}count2value

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

    4int arr[] = {3, 5, 2, 5, 3, 8, 2};5int count[10] = {0};6int n = 7;
    values this step{3: 1, 5: 1, 2: 1} → {3: 1, 5: 2, 2: 1}count5value

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

    4int arr[] = {3, 5, 2, 5, 3, 8, 2};5int count[10] = {0};6int n = 7;
    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}

    4int arr[] = {3, 5, 2, 5, 3, 8, 2};5int count[10] = {0};6int n = 7;
    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}

    4int arr[] = {3, 5, 2, 5, 3, 8, 2};5int count[10] = {0};6int n = 7;
    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

    1#include <stdio.h>
    values this step0i3value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1#include <stdio.h>
    values this step1i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1#include <stdio.h>
    values this step2i2value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1#include <stdio.h>
    values this step3i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1#include <stdio.h>
    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

    1#include <stdio.h>
    values this step5i8value1count[value]yesfound8result{3: 2, 5: 2, 2: 2, 8: 1}count

  16. stdout ← 8

    11if (count[arr[i]] == 1) {12    printf("%d\n", arr[i]);13    break;
    values this step8stdout8result

Complexity

  • Time: O(n) for this checked C source
  • Space: O(1) for the fixed count[10] direct-address table

Implementation notes

  • This checked C source is not a real hash table. It uses direct addressing with int count[10] = {0}, so the input values must be valid indexes into that fixed count array.
  • int arr[] = {3, 5, 2, 5, 3, 8, 2} and count[10] are local stack arrays; n is the literal 7, and there is no helper function where array parameters decay to pointers.
  • There is no hash function, bucket array, sentinel, or collision handling here: count[arr[i]] += 1 maps each value directly to its count slot.
  • The first pass mutates counts in input order, producing trace states from {3: 1} through {3: 2, 5: 2, 2: 2, 8: 1}.
  • The second pass scans the original array order and checks count[arr[i]] == 1; the trace skips 3, 5, 2, 5, and 3, then finds 8 at i=5.
  • printf("%d\n", arr[i]) prints 8 and breaks. Visible memory is the two stack arrays and scalar loop indexes; visible mutation is confined to count.