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 log k) in this C++ source because std::map uses ordered lookup
Space: O(k) for k distinct values

Implementation notes

In C++, the checked source uses std::vector<int> arr with values {3, 5, 2, 5, 3, 8, 2} and std::map<int, int> count; it does not use a string, char keys, or std::unordered_map.
count[value] += 1 uses operator[]: a missing key is value-initialized to 0, then incremented. Existing keys are updated in place.
std::map keeps keys ordered internally, but the selection pass does not iterate the map. It scans arr again, preserving input order for the first non-repeating choice. These are ordered-tree lookups, not average O(1) hash table operations.
The trace records count states from {} through {3: 2, 5: 2, 2: 2, 8: 1}, then scans input indexes until arr[5] == 8 has frequency 1.
std::cout << value << "\n" prints 8 and breaks. Visible allocation is the vector storage and map nodes; mutation is the map count updates.
Because this source uses std::map and never exposes buckets, no hashing or collision behavior is visible in the checked trace.

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.