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.cpp
Replay: real traced execution (multi-file project)
#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;
        }
    }
}

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

    1#include <iostream>2#include <map>
    values this step[3, 5, 2, 5, 3, 8, 2]arr

  2. count ← {}

    7vector<int> arr = {3, 5, 2, 5, 3, 8, 2};8map<int, int> count;9for (int value : arr) {
    values this step{}count

  3. count ← {3: 1}

    7vector<int> arr = {3, 5, 2, 5, 3, 8, 2};8map<int, int> count;9for (int value : arr) {
    values this step{} → {3: 1}count3value

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

    7vector<int> arr = {3, 5, 2, 5, 3, 8, 2};8map<int, int> count;9for (int value : arr) {
    values this step{3: 1} → {3: 1, 5: 1}count5value

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

    7vector<int> arr = {3, 5, 2, 5, 3, 8, 2};8map<int, int> count;9for (int value : arr) {
    values this step{3: 1, 5: 1} → {3: 1, 5: 1, 2: 1}count2value

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

    7vector<int> arr = {3, 5, 2, 5, 3, 8, 2};8map<int, int> count;9for (int value : arr) {
    values this step{3: 1, 5: 1, 2: 1} → {3: 1, 5: 2, 2: 1}count5value

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

    7vector<int> arr = {3, 5, 2, 5, 3, 8, 2};8map<int, int> count;9for (int value : arr) {
    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}

    7vector<int> arr = {3, 5, 2, 5, 3, 8, 2};8map<int, int> count;9for (int value : arr) {
    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}

    7vector<int> arr = {3, 5, 2, 5, 3, 8, 2};8map<int, int> count;9for (int value : arr) {
    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

    12for (int value : arr) {13    if (count[value] == 1) {14        cout << value << "\n";
    values this step0i3value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    12for (int value : arr) {13    if (count[value] == 1) {14        cout << value << "\n";
    values this step1i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    12for (int value : arr) {13    if (count[value] == 1) {14        cout << value << "\n";
    values this step2i2value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    12for (int value : arr) {13    if (count[value] == 1) {14        cout << value << "\n";
    values this step3i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    12for (int value : arr) {13    if (count[value] == 1) {14        cout << value << "\n";
    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

    12for (int value : arr) {13    if (count[value] == 1) {14        cout << value << "\n";
    values this step5i8value1count[value]yesfound8result{3: 2, 5: 2, 2: 2, 8: 1}count

  16. stdout ← 8

    1#include <iostream>2#include <map>
    values this step8stdout8result

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.