Start learning free

LESSON 277 OF 442 · HASH TABLE

Intersection of Two Arrays in Go: O(n + m) with Maps and a Sort

Practice O(n + m) Read the full explanation

Given two integer arrays first and second, return an array of their intersection. Each element in the result must be unique, and the result must be sorted in ascending order.

 

Example 1:

Input: first = [1,2,2,1], second = [2,2]
Output: [2]

Example 2:

Input: first = [4,9,5], second = [9,4,9,8,4]
Output: [4,9]
Explanation: 4 and 9 are in both arrays. Each appears twice in second, but only once in the result.

 

Constraints:

  • 1 <= first.length, second.length <= 1000
  • -1000 <= first[i], second[i] <= 1000
Note:

Your algorithm should run in O(n + m) time, plus the time to sort the shared numbers, where n and m are the lengths of first and second.

STEP 1 OF 11
    Ctrl + Enter to check

    GO · HASH TABLE

    Intersection Of Two Arrays in Go, explained

    Problem overview

    intersection(first []int, second []int) returns the numbers that appear in both slices. Each shared number appears once in the result, however many times it occurs in the inputs, and the result is sorted in ascending order.

    For first = [1, 2, 2, 1] and second = [2, 2] the only shared number is 2, so the answer is [2]. For first = [4, 9, 5] and second = [9, 4, 9, 8, 4], the numbers 4 and 9 are in both. Each appears twice in second but only once in the answer, which is [4, 9].

    Approach: mark one slice, probe it with the other

    Comparing every number of first with every number of second takes O(n * m) steps. A hash table does it faster, because checking whether a number was seen takes O(1) on average.

    The plan has three parts. First, record every number of first in a lookup table. Second, go through second and note each number that is in the table. Third, turn the noted numbers into a sorted slice. Duplicates take care of themselves: marking a number twice changes nothing, and a table that keeps each key once can't list a number twice.

    The third part needs a closer look. Go doesn't give a map's keys in any particular order, and the order even changes from run to run. The answer has to be ascending, so the collected numbers are sorted at the end. The note about time says exactly this: O(n + m) for the scans, plus the time to sort the shared numbers.

    Step by step

    1. Give the inputs shorter names. nums1 := first and nums2 := second copy only the slice headers, not the numbers.
    2. Create the lookup table: seen := make(map[int]bool). Go has no built-in set type, so a map whose values are always true plays that role.
    3. Loop over nums1 with for _, v := range nums1. The _ skips the index.
    4. Mark each number with seen[v] = true.
    5. Create a second table, inter, for the shared numbers. A map keeps each key once, which gives uniqueness for free.
    6. Loop over nums2. Every number is checked against seen.
    7. Record the shared numbers: if seen[v] is true, set inter[v] = true. A number that isn't in seen reads as false, the zero value of bool, so only numbers present in both slices pass.
    8. Allocate the answer with make([]int, 0, len(inter)): length 0, with room for exactly len(inter) numbers, so append never needs to grow it.
    9. Loop over the keys of inter: for v := range inter. With one variable, a range over a map yields the keys.
    10. Append each key with res = append(res, v). append returns the longer slice, so the result is stored back.
    11. Sort and return. sort.Ints(res) sorts in ascending order, in place, and then res is returned.

    The solution in Go

    func intersection(first []int, second []int) []int {
    nums1 := first
    nums2 := second
    seen := make(map[int]bool)
    for _, v := range nums1 {
        seen[v] = true
    }
    inter := make(map[int]bool)
    for _, v := range nums2 {
        if seen[v] {
            inter[v] = true
        }
    }
    res := make([]int, 0, len(inter))
    for v := range inter {
        res = append(res, v)
    }
    sort.Ints(res)
    return res
}

    The Go details worth a closer look:

    • A map as a set. map[int]bool is the usual stand-in for a set. Reading a missing key returns the zero value, false, without adding the key, so if seen[v] needs no separate presence check. Some programs use map[int]struct{} instead, which stores no value at all, but the bool form reads more simply.
    • Random iteration order. The language specification leaves a map's iteration order unspecified, and the Go runtime randomises it. Returning the keys in loop order would give a different order from run to run, which is why sort.Ints is needed.
    • The import. sort.Ints needs import "sort" at the top of the file.
    • Capacity versus length. make([]int, 0, len(inter)) creates an empty slice with spare capacity. With make([]int, len(inter)) the slice would start with that many zeros, and append would add after them.
    • Nothing in common. The result is then an empty, non-nil slice, [], because make always returns a slice with a backing array.
    • Negative numbers. Map keys can be any integer, so values from -1000 up to 1000 need no special handling.

    Complexity

    Let n and m be the lengths of first and second, and r the number of shared distinct numbers.

    Time: O(n + m + r log r). Filling seen costs O(n) and probing with second costs O(m), since each map operation is O(1) on average. Copying the shared keys into the slice costs O(r) and sorting them O(r log r). Since r is at most the smaller of n and m, the sort is the only part that isn't linear.

    Space: O(n + m). seen holds up to n distinct numbers, inter and the answer up to r each.

    Edge cases and common mistakes

    • Duplicates in both slices. [1, 2, 2, 1] and [2, 2] give [2], not [2, 2]. The map lists each number once.
    • No shared numbers. [1] and [2] give an empty slice.
    • Forgetting the sort. The answer may come out in the right order by luck on one run and in another order on the next.
    • Appending inside the second loop. Adding v to the result directly whenever seen[v] is true would list a number once per occurrence in second. The second map filters that out.
    • Discarding the result of append. Writing append(res, v) without assigning it back loses the new element.

    Testing

    • first = [1, 2, 2, 1], second = [2, 2] gives [2].
    • first = [4, 9, 5], second = [9, 4, 9, 8, 4] gives [4, 9].
    • first = [1], second = [2] gives [].
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free