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.

Basic Implementation

basic.lua 
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

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.
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.