Group by Key - Lua DSA

Build buckets keyed by a shared field, preserving the first-seen key order.

Algorithm

Canonical pairs (a,1), (b,2), (a,3), (c,4), (b,5) print {a: [1, 3], b: [2, 5], c: [4]}. 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 pairs_data = {{"a", 1}, {"b", 2}, {"a", 3}, {"c", 4}, {"b", 5}}
local groups = {}
local order = {}
for _, pair in ipairs(pairs_data) do
  local key, value = pair[1], pair[2]
  if groups[key] == nil then
    groups[key] = {}
    table.insert(order, key)
  end
  table.insert(groups[key], value)
end
local parts = {}
for _, key in ipairs(order) do
  table.insert(parts, key .. ": [" .. table.concat(groups[key], ", ") .. "]")
end
print("{" .. table.concat(parts, ", ") .. "}")

Complexity

Time: O(n) average
Space: O(k + n) for buckets and 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.

bucket map Each key owns a list. A new key creates a bucket; a repeated key appends to the existing bucket.