How to Get Intersection of Two Slices In Golang

How to Get Intersection of Two Slices In Go (Golang)

In Golang, a slice is a dynamically sized, contiguous sequence of elements. Slices are often used to store collections of data, such as lists, arrays, and strings. In order to get an intersection of two slices in Go (Golang) you don't need any external library you can use everything that is available already in the Go (Golang) standard library.

There are different approaches to slice intersection in general:

1. Using Two For Loops
2. Using a Map
3. Sorting The Slices

Let's see how to implement the above approaches in Go (Golang).

Using for loops

This is the simplest way to intersect two slices. You will compare each element in the first slice to each element in the second slice. This is also the most inefficient (slowest) of the 3 methods with a time complexity of O(n^2)

package main

import "fmt"

func main() {
	janeTrips := []string{"london", "new york", "malibu"}
	theresaTrips := []string{"jakarta", "malibu", "bora bora", "london"}

	fmt.Println("jane", janeTrips)
	fmt.Println("theresa", theresaTrips)
	commonTrips := make([]string, 0) // interesection
	for _, janeLoc := range janeTrips {
		for _, theresaLoc := range theresaTrips {
			if janeLoc == theresaLoc {
				commonTrips = append(commonTrips, theresaLoc)
			}
		}
	}
	fmt.Println("common", commonTrips)
}

This will yield the following result:

jane [london new york malibu]
theresa [jakarta malibu bora bora london]
common [malibu london]

You can also run this example on the Golang Playground https://go.dev/play/p/81BdAH0Tkms

Using a map

The second method requires us to iterate through the slices and create a map that we can use as a lookup table. Once the first slice is in the map we iterate over the second slice and each element that is present in the map, will be added to the end result. This will be more time efficient than the first approach but will require us to use a bit more space (the space to store items in the map). The time complexity is O(n)

Let's see how it is implemented

package main

import "fmt"

func main() {
	janeTrips := []string{"london", "new york", "malibu"}
	theresaTrips := []string{"jakarta", "malibu", "bora bora", "london"}

	fmt.Println("jane", janeTrips)
	fmt.Println("theresa", theresaTrips)
	janeTripsMap := make(map[string]struct{}, 0)
	for _, location := range janeTrips {
		janeTripsMap[location] = struct{}{}
	}
	commonTrips := make([]string, 0) // interesection
	for _, location := range theresaTrips {
		if _, found := janeTripsMap[location]; found {
			commonTrips = append(commonTrips, location)
		}
	}
	fmt.Println("common", commonTrips)
}

This will yield the following result:

jane [london new york malibu]
theresa [jakarta malibu bora bora london]
common [malibu london]

You can also run this example on the Golang Playground https://go.dev/play/p/1UXquE8NZwk

Sorting the slices

This method is best of both worlds, as we don't use any auxiliary data structure but we improve on the time complexity of our first example. The idea is to first sort the slices in alphabetical order, then iterate through the slices, in a more efficient way. The time complexity is O(n*log(n))

Let's see how this works

package main

import (
	"fmt"
	"sort"
)

func main() {
	janeTrips := []string{"london", "new york", "malibu"}
	theresaTrips := []string{"jakarta", "malibu", "bora bora", "london"}

	fmt.Println("jane", janeTrips)
	fmt.Println("theresa", theresaTrips)

	sort.Strings(janeTrips)
	sort.Strings(theresaTrips)

	commonTrips := make([]string, 0)
	minLen := len(janeTrips)
	if len(theresaTrips) < minLen {
		minLen = len(theresaTrips)
	}
	for i, j := 0, 0; i < len(janeTrips) && j < len(theresaTrips); {
		if janeTrips[i] == theresaTrips[j] {
			commonTrips = append(commonTrips, theresaTrips[j])
			i++
			j++
		} else if janeTrips[i] < theresaTrips[j] {
			i++
		} else {
			j++
		}
	}
	fmt.Println(commonTrips)

}

This will yield the following result:

jane [london new york malibu]
theresa [jakarta malibu bora bora london]
common [malibu london]

You can also run this example on the Golang Playground https://go.dev/play/p/7v--5tGGpeC