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

  • arr <- c(3, 5, 2, 5, 3, 8, 2) is the pinned R vector for this replay.
  • count <- table(arr) builds R's named frequency table. The trace shows it filling from {} through {3: 1}, {3: 1, 5: 1}, and the final {3: 2, 5: 2, 2: 2, 8: 1}.
  • The second pass uses for (value in arr), so it checks values in the original vector order instead of walking the table names.
  • table() stores its names as labels, so lookup uses count[as.character(value)]: numeric 3 is read from the table name "3".
  • Values 3, 5, and 2 are skipped because their counts are 2.
  • When the pass reaches 8, its count is 1; cat(value, "\n", sep = "") prints 8, and break stops the loop.

Replay steps

counts:  {} -> {3:1} -> {3:1,5:1} -> ... -> {3:2,5:2,2:2,8:1}
scan:    3(count 2), 5(count 2), 2(count 2), 5(count 2), 3(count 2)
result:  8(count 1) prints 8
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.