Set Operations using Maps in Go

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.

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.

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 \cdot 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.

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.
}

Instead, maps in Go provide a swift and efficient method for achieving the same result. Here's how you can implement it:

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)$.