How to find intersection of two arrays in GO
In Go a sequence of elements is called a slice. Slices provide the same functionality as an array in other languages. However, slices are dynamic which means their value is not fixed and can be changed, unlike an array.
Array Intersection
The array intersection refers to the collective set of elements that belong to multiple arrays. It represents the common elements between two arrays.
Example
Here the shaded region between the sets A and B represents the intersection of these two sets.
Now let's take another example to understand the concept of intersection.
Array A: [1, 2, 3, 4, 5]Array B: [4, 5, 6, 7, 8]
The intersection of these two arrays would be [4,5] as these two elements are the only elements that belong to both of the sets.
The intersection of arrays in GO
In Go, we can efficiently find the intersection by using the concept of maps and set operations. In this Answer, we will explore a simple and efficient approach to solving this problem.
Brute force approach
The brute force approach can be applied through the following steps.
Create an empty array for returning the result.
Traverse each element in the first array.
Check if it exists in the second array.
If it exists on both arrays, add it to the resultant array.
Implementation
package mainimport ("fmt")func findIntersection(arr1, arr2 []int) []int {intersection := make([]int, 0)// Traverse each element in arr1for _, num1 := range arr1 {// Check if num1 exists in arr2for _, num2 := range arr2 {if num1 == num2 {intersection = append(intersection, num1)break}}}return intersection}func main() {arr1 := []int{1, 2, 3, 4, 5}arr2 := []int{4, 5, 6, 7, 8}result := findIntersection(arr1, arr2)fmt.Println(result) // Output: [4 5]}
Explanation
In this code example, we define a function findIntersection() that finds the intersection between two integer arrays using a brute force approach.
Parameters
indIntersection() takes two integer arrays, arr1 and arr2, as input and returns an array called intersection containing the intersection of the two arrays.
Working
At the start of the function, we initialize an array called intersection and assign 0 to each index.
Lines 11–19: We traverse each element
num1in the first arrayarr1using a range loop. Within the outer loop, it traverses each elementnum2in the second arrayarr2using another range loop.Lines 14–17: If a common element is found,
num1is added to theintersectionarray using theappend()function and then come out of the loop.Lines 24–30: We define two example arrays,
arr1,arr2, and call thefindIntersectionfunction. The resulting intersection is stored in theresultvariable and printed to the console.
Time complexity
The overall time complexity of finding the intersection using the brute force approach is
Where m and n are the sizes of the two arrays.
Efficient approach
We can find the intersection between two arrays by following these simple steps.
Create a set from the first array.
Check if each element exists in the set by traversing through the second array.
If an element exists in both arrays, add it to the intersection array.
Return the intersection array.
Implementation
package mainimport ("fmt")// function for finding the intersection of two arraysfunc findIntersection(arr1, arr2 []int) []int {intersection := make([]int, 0)set := make(map[int]bool)// Create a set from the first arrayfor _, num := range arr1 {set[num] = true // setting the initial value to true}// Check elements in the second array against the setfor _, num := range arr2 {if set[num] {intersection = append(intersection, num)}}return intersection}func main() {arr1 := []int{1, 2, 3, 4, 5} // First input arrayarr2 := []int{4, 5, 6, 7, 8} // Second input arrayresult := findIntersection(arr1, arr2)fmt.Println("The intersection between the two input arrays is",result) // Printing the output}
Explanation
In this code example, we define a function findIntersection() that finds the intersection between two integer arrays using an efficient approach through sets and maps.
Parameters
indIntersection() takes two integer arrays, arr1 and arr2, as input and returns an array called intersection containing the intersection of the two arrays.
Working
At the start of the function, we initialize the intersection array to store the result going forward. Then, we create a set using a map data structure where the keys represent the elements of the first array.
Lines 12–15: We assign
trueto each key, effectively creating a set of unique elements fromarr1.Lines 17–22: We traverse
arr2and check if each element exists in theset. If an element exists, we append it to theintersectionarray.Lines 24: We return the
intersectionarray which contains all the common elements betweenarr1andarr2.Lines 27–32: We define two example arrays,
arr1,arr2, and call thefindIntersectionfunction. The resulting intersection is stored in theresultvariable and printed to the console.
Time complexity
The overall time complexity of finding the intersection using sets and maps is
Where m and n are the sizes of the two arrays.
This is because the time complexity of creating the set is O(m), and the time complexity of checking the elements in the second array against the set is O(n).
Summary
Go provides a straightforward and convenient method to find the intersection between two arrays. The approach defined above involves maps to create a set of an array, which greatly eases the process of finding the intersection between arrays in Go.
Free Resources
