Set Operations using Maps in Go

Introduction to Operating Sets 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.

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

O(n \cdot m)

Efficient Approach

O(n)

Join the 1M+ learners on CodeSignal

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

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

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
}

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
}

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
}

Introduction to Operating Sets in Go

Problem 1: Check if Two Sets are Disjoint

Naive Approach

Efficient Approach

Join the 1M+ learners on CodeSignal

Problem 2: Remove Duplicates from an Array

Naive Approach

Efficient Approach

Lesson Summary