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"]
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
}
Another O(m+n) Time Complexity solution that uses a hashmap. It has two differences compared to the other solutions discussed here.
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
Try it
https://go.dev/play/p/eGGcyIlZD6y
first := []string{"one", "two", "three", "four"}
second := []string{"two", "four"}
result := intersection(first, second) // or intersection(second, first)
func intersection(first, second []string) []string {
out := []string{}
bucket := map[string]bool{}
for _, i := range first {
for _, j := range second {
if i == j && !bucket[i] {
out = append(out, i)
bucket[i] = true
}
}
}
return out
}