# Array Intersection

# 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.

```id="array-intersection-distinct"
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.

```id="array-intersection-multiset"
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

```python id="array-intersection-python"
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
```

```go id="array-intersection-go"
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
}
```