Group by Key

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

Basic Implementation

basic.R

keys <- c("a", "b", "a", "c", "b")
values <- c(1, 2, 3, 4, 5)
groups <- list()
order <- c()
for (i in seq_along(keys)) {
  key <- keys[[i]]
  if (is.null(groups[[key]])) {
    groups[[key]] <- c()
    order <- c(order, key)
  }
  groups[[key]] <- c(groups[[key]], values[[i]])
}
parts <- sapply(order, function(key) paste0(key, ": [", paste(groups[[key]], collapse = ", "), "]"))
cat("{", paste(parts, collapse = ", "), "}\n", sep = "")

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.