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 R DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.R 
arr <- c(3, 5, 2, 5, 3, 8, 2)
count <- table(arr)
for (value in arr) {
  if (count[as.character(value)] == 1) {
    cat(value, "\n", sep = "")
    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.