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.

Basic Implementation

basic.c

#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;
        }
    }
}

Complexity

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

Implementation notes

Keep output formatting deterministic. Do not rely on unordered hash-map printing when the lesson needs cross-language comparison.
The trace highlights the hash table state after each write.

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.