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 Lua 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.lua
Replay: real traced execution (multi-file project)
local arr = {3, 5, 2, 5, 3, 8, 2}
local count = {}
for _, value in ipairs(arr) do
  count[value] = (count[value] or 0) + 1
end
for _, value in ipairs(arr) do
  if count[value] == 1 then
    print(value)
    break
  end
end

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

    1local arr = {3, 5, 2, 5, 3, 8, 2}2local count = {}
    values this step[3, 5, 2, 5, 3, 8, 2]arr

  2. count ← {}

    1local arr = {3, 5, 2, 5, 3, 8, 2}2local count = {}3for _, value in ipairs(arr) do
    values this step{}count

  3. count ← {3: 1}

    1local arr = {3, 5, 2, 5, 3, 8, 2}2local count = {}3for _, value in ipairs(arr) do
    values this step{} → {3: 1}count3value

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

    1local arr = {3, 5, 2, 5, 3, 8, 2}2local count = {}3for _, value in ipairs(arr) do
    values this step{3: 1} → {3: 1, 5: 1}count5value

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

    1local arr = {3, 5, 2, 5, 3, 8, 2}2local count = {}3for _, value in ipairs(arr) do
    values this step{3: 1, 5: 1} → {3: 1, 5: 1, 2: 1}count2value

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

    1local arr = {3, 5, 2, 5, 3, 8, 2}2local count = {}3for _, value in ipairs(arr) do
    values this step{3: 1, 5: 1, 2: 1} → {3: 1, 5: 2, 2: 1}count5value

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

    1local arr = {3, 5, 2, 5, 3, 8, 2}2local count = {}3for _, value in ipairs(arr) do
    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}

    1local arr = {3, 5, 2, 5, 3, 8, 2}2local count = {}3for _, value in ipairs(arr) do
    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}

    1local arr = {3, 5, 2, 5, 3, 8, 2}2local count = {}3for _, value in ipairs(arr) do
    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

    6for _, value in ipairs(arr) do7  if count[value] == 1 then8    print(value)
    values this step0i3value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    6for _, value in ipairs(arr) do7  if count[value] == 1 then8    print(value)
    values this step1i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    6for _, value in ipairs(arr) do7  if count[value] == 1 then8    print(value)
    values this step2i2value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    6for _, value in ipairs(arr) do7  if count[value] == 1 then8    print(value)
    values this step3i5value2count[value]nofound{3: 2, 5: 2, 2: 2, 8: 1}count

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

    6for _, value in ipairs(arr) do7  if count[value] == 1 then8    print(value)
    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

    6for _, value in ipairs(arr) do7  if count[value] == 1 then8    print(value)
    values this step5i8value1count[value]yesfound8result{3: 2, 5: 2, 2: 2, 8: 1}count

  16. stdout ← 8

    7if count[value] == 1 then8  print(value)9  break
    values this step8stdout8result

Complexity

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

Implementation notes

  • The checked Lua input is the numeric table local arr = {3, 5, 2, 5, 3, 8, 2}.
  • local count = {} is the frequency table, keyed by the numeric values from arr.
  • The first pass uses for _, value in ipairs(arr) do, so it follows the dense table's 1-based order.
  • Missing Lua table keys read as nil; (count[value] or 0) + 1 treats a missing count as zero before incrementing.
  • The trace grows the count table through {3: 1}, {3: 1, 5: 1}, {3: 1, 5: 1, 2: 1}, then finishes at {3: 2, 5: 2, 2: 2, 8: 1}.
  • The second pass scans arr again with ipairs, not by iterating the count table, so original input order decides the first unique value.
  • The replay labels scan positions in zero-based form: arr[0] value 3, arr[1] value 5, arr[2] value 2, arr[3] value 5, and arr[4] value 3 all have frequency 2.
  • At the next value, 8, count[value] == 1 succeeds, so print(value) runs and break stops before the final 2.
  • The only printed output in this checked run is 8.