Welcome back! Building on our previous unit, today we're diving into Go's approach to set operations using maps. Similar to how a club assigns unique membership IDs, maps ensure each key is unique. Throughout the session, you'll see how maps can simplify tasks involving ensuring uniqueness and checking set intersections. Let's explore how maps can transform lengthy, cumbersome operations into efficient, elegant code.
Problem 1: Check if Two Sets are Disjoint
Imagine you're developing a feature for a social media platform that requires user groups to be exclusive — you need to ensure that users can't belong to more than one group at a time. It's like organizing events where a guest should not appear on the lists for two different parties at the same venue — an overlap would be a significant issue.
Naive Approach
Initially, you might consider checking for overlap by comparing each member of one group with every member of the other — a somewhat cumbersome O(n⋅m) operation. If you have hundreds or thousands of users in each group, the time it would take to compare them all grows exponentially. This approach is impractical and resource-intensive, especially on the scale of a social media platform with potentially millions of users.
Go
func AreDisjoint(arr1, arr2 []int) bool { for _, num1 := range arr1 { for _, num2 := range arr2 { if num1 == num2 { return false // An overlap is found. } } } return true // No overlaps found, sets are disjoint.}
Efficient Approach
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal
Instead, maps in Go provide a swift and efficient method for achieving the same result. Here's how you can implement it:
Go
func AreDisjoint(arr1, arr2 []int) bool { set1 := make(map[int]struct{}) for _, num := range arr1 { set1[num] = struct{}{} // Populate the map using struct{} to save space } for _, num := range arr2 { if _, exists := set1[num]; exists { return false // If found, the sets are not disjoint. } } return true}
Notice the _, exists := set1[num]; exists part of the if statement. It checks if num is a key in set1. It assigns the value associated with num and a boolean exists indicating whether the key exists. The underscore _ ignores the actual value retrieved, focusing instead on the existence of the key for control flow.
Using maps with struct{} provides significant speed advantages while minimizing memory usage. First, we iterate over arr1 to populate set1, marking each element. This operation takes O(n) time, where n is the length of arr1. Then, it iterates over arr2, checking if any element exists in set1. The existence check in a map is a constant-time operation, O(1), resulting in an overall time complexity of O(m) for the second loop, where m is the length of arr2. Thus, the overall time complexity of the function is O(n+m).
Problem 2: Remove Duplicates from an Array
Consider a scenario where you have a list of email addresses but must ensure each customer receives only one newsletter — duplicates must go. This scenario is akin to managing invitations to an exclusive gala, where each person should receive only one invite, meaning the invitation list must be free of repeats.
Naive Approach
Efficient Approach
Lesson Summary
Reflecting on today's lesson, we've explored the practical utility of Go's maps to achieve set operations, transitioning a conversation about uniqueness into user-friendly and optimal code. We delved into two practical examples, evaluating the pitfalls of naive implementations and recognizing the benefits of using maps to overcome them efficiently and gracefully. The key takeaway is the importance of optimizing operations for large datasets with maps’ efficient membership checks. With this newfound appreciation for maps, it's time for practice!
The naive approach to this problem would be to create a new list and check every incoming address against all previously added ones — resulting in an inefficient O(n2) operation. Such an approach would not scale well with larger datasets and could lead to significant delays.
Go
func RemoveDuplicates(arr []int) []int { uniqueList := []int{} for _, num := range arr { contains := false for _, uniqueNum := range uniqueList { if num == uniqueNum { contains = true break } } if !contains { uniqueList = append(uniqueList, num) // Add number if it's not already in the list } } return uniqueList}
By using a map's inherent capability to prevent duplicates, we can effectively streamline the process:
Go
func RemoveDuplicates(arr []int) []int { nums := make(map[int]struct{}) for _, num := range arr { nums[num] = struct{}{} // Add the number if it's not already present, ignoring duplicates } result := make([]int, 0, len(nums)) for num := range nums { result = append(result, num) // Each unique element is added to the result slice } return result}
RemoveDuplicates first iterates through the array, adding each element to nums, which takes O(n). Since map insertion is an average O(1) operation, duplicates are inherently ignored. Then, we construct the result slice, iterating over the keys of nums, which also takes O(n) time in the worst case. Consequently, the overall time complexity of the function is O(n).
Now we have a clean list ready for our exclusive newsletter send-out. The map optimizes our process, scaling efficiently for larger datasets.
