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

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {3, 5, 2, 5, 3, 8, 2};
    map<int, int> count;
    for (int value : arr) {
        count[value] += 1;
    }
    for (int value : arr) {
        if (count[value] == 1) {
            cout << value << "\n";
            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.