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

Basic Implementation

basic.scala

import scala.collection.mutable.{HashMap, ArrayBuffer}
object Main {
  def main(args: Array[String]): Unit = {
    val pairs = List(("a", 1), ("b", 2), ("a", 3), ("c", 4), ("b", 5))
    val groups = HashMap.empty[String, ArrayBuffer[Int]]
    val order = ArrayBuffer.empty[String]
    for ((key, value) <- pairs) {
      if (!groups.contains(key)) {
        groups(key) = ArrayBuffer.empty[Int]
        order += key
      }
      groups(key) += value
    }
    val parts = order.map(key => s"$key: [${groups(key).mkString(", ")}]")
    println("{" + parts.mkString(", ") + "}")
  }
}

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.