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 Rust 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.rs
Replay: real traced execution (multi-file project)
use std::collections::HashMap;

fn main() {
    let arr = [3, 5, 2, 5, 3, 8, 2];
    let mut count: HashMap<i32, i32> = HashMap::new();
    for value in arr {
        *count.entry(value).or_insert(0) += 1;
    }
    for value in arr {
        if count[&value] == 1 {
            println!("{}", value);
            break;
        }
    }
}

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

    1use std::collections::HashMap;
    values this step[3, 5, 2, 5, 3, 8, 2]arr

  2. count ← {}

    4let arr = [3, 5, 2, 5, 3, 8, 2];5let mut count: HashMap<i32, i32> = HashMap::new();6for value in arr {
    values this step{}count

  3. count ← {3: 1}

    4let arr = [3, 5, 2, 5, 3, 8, 2];5let mut count: HashMap<i32, i32> = HashMap::new();6for value in arr {
    values this step{} → {3: 1}count3value

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

    4let arr = [3, 5, 2, 5, 3, 8, 2];5let mut count: HashMap<i32, i32> = HashMap::new();6for value in arr {
    values this step{3: 1} → {3: 1, 5: 1}count5value

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

    4let arr = [3, 5, 2, 5, 3, 8, 2];5let mut count: HashMap<i32, i32> = HashMap::new();6for value in arr {
    values this step{3: 1, 5: 1} → {3: 1, 5: 1, 2: 1}count2value

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

    4let arr = [3, 5, 2, 5, 3, 8, 2];5let mut count: HashMap<i32, i32> = HashMap::new();6for value in 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}

    4let arr = [3, 5, 2, 5, 3, 8, 2];5let mut count: HashMap<i32, i32> = HashMap::new();6for value in 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}

    4let arr = [3, 5, 2, 5, 3, 8, 2];5let mut count: HashMap<i32, i32> = HashMap::new();6for value in 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}

    4let arr = [3, 5, 2, 5, 3, 8, 2];5let mut count: HashMap<i32, i32> = HashMap::new();6for value in 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

    1use std::collections::HashMap;
    values this step0i3value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1use std::collections::HashMap;
    values this step1i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1use std::collections::HashMap;
    values this step2i2value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1use std::collections::HashMap;
    values this step3i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    1use std::collections::HashMap;
    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

    1use std::collections::HashMap;
    values this step5i8value1count[value]yesfound8result{3: 2, 5: 2, 2: 2, 8: 1}count

  16. stdout ← 8

    10if count[&value] == 1 {11    println!("{}", value);12    break;
    values this step8stdout8result

Complexity

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

Implementation notes

  • The checked source imports std::collections::HashMap and uses let mut count: HashMap<i32, i32> = HashMap::new(); there is no string or char iteration in this Rust lesson.
  • The input is the fixed integer array [3, 5, 2, 5, 3, 8, 2]. Because the elements are i32 copies, for value in arr copies each value into the loop.
  • Counting uses *count.entry(value).or_insert(0) += 1. entry owns the copied key, or_insert(0) creates missing counts, and the dereference mutates the stored i32 count in place.
  • The trace records counts growing through {3: 1}, {3: 1, 5: 1}, {3: 1, 5: 1, 2: 1}, then updating repeats to the final {3: 2, 5: 2, 2: 2, 8: 1}.
  • The second pass also iterates over arr, so first-non-repeating order comes from the original array, not from hash-map iteration order.
  • Lookup uses indexing syntax count[&value], borrowing the copied loop value as the key. No Option sentinel is exposed here; the first pass has inserted every value before the scan.
  • The scan skips indices 0 through 4 with frequency 2, finds 8 at index 5, prints it with println!("{}", value), and breaks before the final 2.
  • The trace exposes count-table states only; it does not show bucket placement or collision behavior.