Working with Scala Sets

Greetings, programming enthusiast! In this unit, we're embarking on a thrilling numerical quest, where mysterious bridges connect the islands of data. On these bridges, we'll encounter hashes and bins, all converging into sets! Throughout our journey, we'll utilize the fundamental concepts of Scala's built-in collection type, the Set, to formulate an optimal solution. So, fasten your seatbelt and get ready to solve problems using Scala's powerful collections!

The task for this unit is to devise a Scala function that accepts two lists containing unique integers and returns another list containing the elements common to both input lists. This task provides an intriguing perspective on deriving similarities between two data sequences, a scenario commonly encountered in data comparisons and analytics.

For illustration, suppose we're given two lists:

val list1 = List(1, 2, 3, 5, 8, 13, 21, 34)
val list2 = List(2, 3, 5, 7, 13, 21, 31)

The commonElements(list1, list2) function should comb through these sequences of integers and extract the common elements between them.

The expected outcome in this case should be:

List(2, 3, 5, 13, 21)

Before we delve into the optimized solution, it is instrumental to consider a basic or naïve approach to this problem and analyze its complexity. Our first intuitive approach is to iterate through the first list and, for each element, check if it exists in the second list. If it's found, we add it to our result list.

def commonElementsSlow(list1: List[Int], list2: List[Int]): List[Int] = {
  list1.filter(num1 => list2.contains(num1))
}

However, the problem with this approach lies in its efficiency. The contains method on a list performs a linear search, so for each element in list1, we potentially traverse through all elements in list2. This gives us an $O(n \times m)$ solution, where n and m represent the number of elements in list1 and list2, respectively. For large lists, this iterative approach tends to be inefficient and slow, making it a less desirable solution for this problem.

The solution we aim to implement in the following section utilizes a set data structure to optimize our algorithm and reach a solution in markedly less computational time.