Array Intersection

Array intersection returns the elements that appear in both input arrays. The result can be defined as a set of distinct values or as a multiset that preserves counts.

You use it when you need to find overlap between datasets.

Problem

Given arrays $A$ and $B$ , compute:

A \cap B

Two common variants:

distinct intersection: each value appears once
multiset intersection: each value appears $\min(count_A, count_B)$ times

Algorithm

For distinct intersection, use a set.

intersection_distinct(A, B):
    S = set of elements in A
    R = empty array

    for x in B:
        if x in S:
            append x to R
            remove x from S

    return R

For multiset intersection, count occurrences.

intersection_multiset(A, B):
    count = map from value to frequency in A
    R = empty array

    for x in B:
        if count[x] > 0:
            append x to R
            count[x] -= 1

    return R

Example

Let

A = [8, 3, 5, 3]

and

B = [3, 3, 8, 1]

Distinct intersection:

step	element	result
1	3	[3]
2	3	skip
3	8	[3, 8]
4	1	skip

Result:

[3, 8]

Multiset intersection:

step	element	count left	result
1	3	1	[3]
2	3	0	[3, 3]
3	8	0	[3, 3, 8]
4	1	0	[3, 3, 8]

Result:

[3, 3, 8]

Correctness

For the distinct version, the set contains elements of $A$ . Each time a value from $B$ appears in the set, it is added once and removed, preventing duplicates.

For the multiset version, the map tracks how many times each value can still be used. Each match decreases the count, ensuring that the result contains exactly the minimum frequency across both arrays.

Complexity

variant	time	space
distinct	$O(n + m)$	$O(n)$
multiset	$O(n + m)$	$O(n)$

When to Use

Array intersection is appropriate when:

finding common elements between datasets
comparing records or keys
computing overlaps

If both arrays are sorted, a two-pointer method can compute the intersection in:

O(n + m)

time with:

O(1)

extra space.

Implementation

def intersection_distinct(a, b):
    s = set(a)
    result = []

    for x in b:
        if x in s:
            result.append(x)
            s.remove(x)

    return result

def intersection_multiset(a, b):
    from collections import Counter
    count = Counter(a)
    result = []

    for x in b:
        if count[x] > 0:
            result.append(x)
            count[x] -= 1

    return result

func IntersectionDistinct(a, b []int) []int {
    s := make(map[int]struct{})
    for _, x := range a {
        s[x] = struct{}{}
    }

    result := []int{}

    for _, x := range b {
        if _, ok := s[x]; ok {
            result = append(result, x)
            delete(s, x)
        }
    }

    return result
}

func IntersectionMultiset(a, b []int) []int {
    count := make(map[int]int)
    for _, x := range a {
        count[x]++
    }

    result := []int{}

    for _, x := range b {
        if count[x] > 0 {
            result = append(result, x)
            count[x]--
        }
    }

    return result
}