How to get intersection of two slice in golang?

Question

Is there any efficient way to get intersection of two slices in Go?

I want to avoid nested for loop like solution

slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar"}

intersection(slice1, slice2)
=> ["foo", "bar"]

order of string does not matter

Answer 1

How do I get the intersection between two arrays as a new array?

• Simple Intersection: Compare each element in A to each in B (O(n^2))
• Hash Intersection: Put them into a hash table (O(n))
• Sorted Intersection: Sort A and do an optimized intersection (O(n*log(n)))

All of which are implemented here

https://github.com/juliangruber/go-intersect

Answer 2

It's a best method for intersection two slice. Time complexity is too low.

Time Complexity : O(m+n)

m = length of first slice.

n = length of second slice.

func intersection(s1, s2 []string) (inter []string) {
    hash := make(map[string]bool)
    for _, e := range s1 {
        hash[e] = true
    }
    for _, e := range s2 {
        // If elements present in the hashmap then append intersection list.
        if hash[e] {
            inter = append(inter, e)
        }
    }
    //Remove dups from slice.
    inter = removeDups(inter)
    return
}

//Remove dups from slice.
func removeDups(elements []string)(nodups []string) {
    encountered := make(map[string]bool)
    for _, element := range elements {
        if !encountered[element] {
            nodups = append(nodups, element)
            encountered[element] = true
        }
    }
    return
}

Answer 3

if there exists no blank in your []string, maybe you need this simple code:

func filter(src []string) (res []string) {
    for _, s := range src {
        newStr := strings.Join(res, " ")
        if !strings.Contains(newStr, s) {
            res = append(res, s)
        }
    }
    return
}

func intersections(section1, section2 []string) (intersection []string) {
    str1 := strings.Join(filter(section1), " ")
    for _, s := range filter(section2) {
        if strings.Contains(str1, s) {
            intersection = append(intersection, s)
        }
    }
    return
}

Answer 4

simple, generic and mutiple slices ! (Go 1.18)

Time Complexity : may be linear

package main
import (
  "fmt"
  "golang.org/x/exp/constraints"
)
    
func interSection[T constraints.Ordered](pS ...[]T) (result []T) {
  hash := make(map[T]*int) // value, counter
  for _, slice := range pS {
    for _, value := range slice {
      if counter := hash[value]; counter != nil {
        *counter++
      } else {
        i := 1
        hash[value] = &i
      }
    }
  }
  result = make([]T, 0)
  for value, counter := range hash {
    if *counter >= len(pS) {
      result = append(result, value)
    }
  }
  return
}
    
func main() {
  slice1 := []string{"foo", "bar", "hello"}
  slice2 := []string{"foo", "bar"}
  fmt.Println(interSection(slice1, slice2))
  // [foo bar]

  ints1 := []int{1, 2, 3, 9}
  ints2 := []int{10, 4, 2, 4, 8, 9}
  ints3 := []int{2, 4, 8, 1}
  fmt.Println(interSection(ints1, ints2, ints3))
  // [2 4]
}

playground : https://go.dev/play/p/AFpnUvWHV50