Greetings, programming enthusiast! In this lesson, we're embarking on a thrilling numerical quest where bridges connect 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 Ruby's Set class to formulate an optimal solution. So, fasten your seatbelt and get ready to solve problems!
Task Statement
The task for this unit is to devise a Ruby method that accepts two arrays containing unique integers and returns another array containing the elements common to both input arrays. This task provides an intriguing perspective on deriving similarities between two data sequences, a scenario commonly encountered in data comparisons and analytics.
The common_elements(array1, array2) method should search through these arrays of integers and extract the common elements between them.
The expected outcome in this case should be:
[2, 3, 5, 13, 21]
Brute Force Solution and Complexity Analysis
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. Often, our first intuitive approach is to iterate over both arrays in nested loops and find common elements. This way, for each element in the first array, we check for its presence in the second array. If it's found, it is added to our result array. Let's see how such a solution would look:
def common_elements_slow(array1, array2) common = [] # array to store common elements array1.each do |num1| array2.each do |num2| if num1 == num2 common << num1 break # break inner loop as we found the number in array2 end end end commonend
However, the problem with this approach lies in its efficiency. Given that the worst-case scenario has us traversing through every element in both arrays, we refer to this as an O(n*m) solution, where n and m represent the number of elements in array1 and array2, respectively. For large arrays, 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 a markedly less computational time.
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal
Ruby
[2, 3, 5, 13, 21]
Ruby
def common_elements_slow(array1, array2) common = [] # array to store common elements array1.each do |num1| array2.each do |num2| if num1 == num2 common << num1 break # break inner loop as we found the number in array2 end end end commonend
Introduction to Set Solution
Solution Building: Step 1
Solution Building: Step 2
Solution Building: Step 3
Additional Set Methods
The Set class in Ruby is not only efficient but also provides a plethora of useful methods for performing various operations. Let's explore some of these operations:
Union (|): The union is a method or operation that combines all unique elements from two sets. Essentially, the resultant set will contain all elements present in both sets.
Knowing these operations will allow you to use Ruby sets to their full potential and help you devise efficient solutions for a variety of problems.
The Power of `include?` with Sets
Ruby's Set class gives us a powerful capability for checking membership using the include? method. The performance of membership operations with sets in Ruby is very efficient compared to arrays.
In this code, my_set.include?(3) checks if 3 is present in my_set and returns true if it exists, false otherwise. Similarly, my_set.include?(6) checks for 6 in my_set, and since it doesn't exist in the set, it returns false.
The magic lies in the time complexity of this process. The include? method works in constant time, O(1), when used with sets. This is contrasted with its counterpart in arrays that works in linear time, O(n).
Lesson Summary
Well done! You've demonstrated a commendable understanding of arrays and sets, along with their operations in Ruby. It is rare to come across solutions that marry elegance with performance efficiency, but today's task offered us precisely that opportunity, and you've seized it superbly.
Of course, the journey doesn't end here. Now, it's time for you to explore similar challenges in the following practice session. Don't be afraid to experiment with various data sequences and maximize your learning venture. Happy coding!
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 Set class provided by Ruby comes to our rescue here.
Sets internally use a hash table data structure, which allows operations like addition, removal, and search to be performed in constant time (on average), i.e., O(1). They also provide a direct method, &, to find common elements which are 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. Since we need to sort the result in the end, it makes the total complexity of the algorithm O(min(n,m)log(min(n,m))). This is because the intersection & only needs to iterate over the smaller set, while sorting an array of size k (where k = min(n,m)) has a complexity of O(klogk). However, it is still better than O(n⋅m).
Let's proceed to building this optimized solution in the next section.
The initial step in crafting our solution is to transform these arrays into Ruby's Set datatype. The computation of operations, like intersection, union, and difference, is highly optimized in sets. Let's leverage this optimization to our advantage.
Converting arrays to sets enables us to leverage hash-based lookups for efficient intersection. This step takes O(n) and O(m) for array1 and array2, respectively.
Having converted our data structure from an array to a set, we're now ready to identify the common elements between the two datasets. The Ruby Set operation & allows us to perform the intersection operation seamlessly and swiftly.
The & operator performs an intersection of the two sets in O(min(n,m)) time. It efficiently checks for membership using hash lookups, avoiding the need for nested iterations.
In this final step, we convert our set of common elements back into an array and sort the integers in ascending order. The sort method in Ruby sorts a sequence and returns a new sorted array.
Converting the set back to an array and sorting it ensures the output is ordered. The sorting step adds O(klogk) complexity, where k is the size of the intersection.
And there you have it, the solution is duly wrapped and ready!
