Working with Scala Sets

Working with Scala Sets | CodeSignal Learn

Introduction

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!

Task Statement

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: Scala 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: Scala List(2, 3, 5, 13, 21)

Brute Force Solution and Complexity Analysis

O(n \times m)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

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.

Scala

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.

Solution Building: Step 1

The initial step in crafting our solution is to transform these lists into Scala's built-in collection type: Set . The computation of operations, like intersection, union, and difference, is highly optimized in sets. We'll leverage this optimization to our advantage. Scala def commonElements(list1: List[Int], list2: List[Int]): List[Int] = {val set1 = list1.toSet val set2 = list2.toSet // Next steps will follow List()} def commonElements(list1: List[Int], list2: List[Int]): List[Int] = {val set1 = list1.toSet val set2 = list2.toSet // Next steps will follow List()}

Solution Building: Step 2

Having converted our data structure from a list to a set, we're now ready to identify the common elements between the two datasets. The Scala set method intersect allows us to perform the intersection operation seamlessly and swiftly. Scala def commonElements(list1: List[Int], list2: List[Int]): List[Int] = {val set1 = list1.toSet val set2 = list2.toSet val common = set1.intersect(set2) // Next step: convert to list and sort List()} def commonElements(list1: List[Int], list2: List[Int]): List[Int] = {val set1 = list1.toSet val set2 = list2.toSet val common = set1.intersect(set2) // Next step: convert to list and sort List()}

Solution Building: Step 3

In this final step, we convert our set of common elements back into a list and sort the integers in ascending order. The toList method in Scala converts a set to a list, and the sorted method sorts the list in ascending order, leaving the original set untouched. Scala def commonElements(list1: List[Int], list2: List[Int]): List[Int] = {val set1 = list1.toSet val set2 = list2.toSet val common = set1.intersect(set2) common.toList.sorted} def commonElements(list1: List[Int], list2: List[Int]): List[Int] = {val set1 = list1.toSet val set2 = list2.toSet val common = set1.intersect(set2) common.toList.sorted} And there you have it, the solution is duly wrapped and ready!

Additional Set Methods

The Power of "contains" with Sets

Scala's Set collection hands us a powerful capability for checking membership using the contains method. The performance of membership operations with sets in Scala is much faster compared to lists. Let's understand this with a simple code snippet: Scala val mySet = Set(1, 2, 3, 4, 5) println(mySet.contains(3)) // prints: true println(mySet.contains(6)) // prints: false val mySet = Set(1, 2, 3, 4, 5) println(mySet.contains(3)) // prints: true println(mySet.contains(6)) // prints: false In this code, mySet.contains(3) checks if 3 is present in mySet and returns true if it exists, false otherwise. Similarly, mySet.contains(6) checks for 6 in mySet, and as it doesn't exist in the set, it returns false . The efficiency lies in the time complexity of this process. The contains method works in constant time, O(1), when used with sets. This is contrasted with its counterpart in lists, which works in linear time, O(n).

Since efficiency is a concern in our previous approach, we want to reduce the time complexity by minimizing the number of operations we perform to reach a solution. The data structure Set provided by Scala comes to our rescue here.

Sets in Scala are implemented using hash tables, which allow operations like addition, removal, and search to be performed in constant time on average, i.e., $O(1)$ . They also provide a direct method, intersect, to find common elements, which is executed in linear time, i.e., $O(\min(n, m))$ . Thus, opting for our approach using sets can significantly reduce our time complexity compared to our iterative approach.

Let's break down the complexity of our set-based solution:

Converting lists to sets: $O(n + m)$
Set intersection: $O(\min(n, m))$
Sorting the intersection result: $O(r \log r)$ where $r$ is the size of the intersection and $r \leq \min(n, m)$

This gives us a total complexity of $O(n + m + r \log r)$ , which is still significantly better than the $O(n \times m)$ brute force approach, especially when the intersection size $r$ is small.

Let's proceed to build this optimized solution in the next section.