# LeetCode 350: Intersection of Two Arrays II

## Problem Restatement

We are given two integer arrays, `nums1` and `nums2`.

Return their intersection.

Unlike LeetCode 349, duplicates matter here. Each element in the result must appear as many times as it appears in both arrays. More precisely, if a value appears `a` times in `nums1` and `b` times in `nums2`, it should appear:

```text
min(a, b)
```

times in the answer.

The result may be returned in any order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integer arrays `nums1` and `nums2` |
| Output | Intersection array with duplicate counts preserved |
| Duplicate rule | Use the minimum count from both arrays |
| Order | Any order is accepted |

Function shape:

```python
def intersect(nums1: list[int], nums2: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

```text
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
```

The value `2` appears twice in both arrays, so it appears twice in the result.

Example 2:

```text
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
```

The value `4` appears once in `nums1` and twice in `nums2`, so it appears once.

The value `9` also appears once in `nums1` and twice in `nums2`, so it appears once.

The result may also be:

```text
[9,4]
```

because order does not matter.

## First Thought: Compare Every Pair

A direct method is to compare elements from both arrays and mark matches.

But once we match a number from `nums2`, we must avoid using that same occurrence again.

This leads to extra bookkeeping and can still take:

```text
O(n * m)
```

time.

A frequency map gives a cleaner solution.

## Key Insight

Count how many times each value appears in one array.

Then scan the other array.

When we see a value that still has remaining count, it belongs in the intersection.

After using it, decrease its count by one.

This exactly enforces the `min(count1, count2)` rule.

To save memory, count the smaller array.

## Algorithm

1. If `nums1` is larger than `nums2`, swap them.
2. Count frequencies of values in the smaller array.
3. Create an empty answer list.
4. Scan the larger array.
5. For each value:
   1. If its count is greater than `0`, append it to the answer.
   2. Decrease its count.
6. Return the answer.

## Walkthrough

Use:

```text
nums1 = [1,2,2,1]
nums2 = [2,2]
```

Count the smaller array:

```text
nums2 -> {2: 2}
```

Scan `nums1`.

Read `1`.

```text
count[1] = 0
```

Skip it.

Read `2`.

```text
count[2] = 2
```

Append `2`, then decrease:

```text
count[2] = 1
answer = [2]
```

Read another `2`.

Append again:

```text
count[2] = 0
answer = [2,2]
```

Read `1`.

Skip it.

Final answer:

```text
[2,2]
```

## Correctness

The frequency map stores how many unused occurrences of each value are available from one array.

When the algorithm scans the other array, it appends a value only if the map says that at least one matching occurrence remains.

Each append consumes exactly one occurrence by decreasing the count.

Therefore, a value can be appended no more times than it appears in the counted array.

It also cannot be appended more times than it appears in the scanned array, because the scanned array is processed one occurrence at a time.

So each value appears in the result exactly the minimum of its two input counts.

Every value with common occurrences is appended whenever those matching occurrences are found during the scan.

Therefore, the algorithm returns exactly the multiset intersection of the two arrays.

## Complexity

Let:

```text
n = len(nums1)
m = len(nums2)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + m)` | Count one array and scan the other |
| Space | `O(min(n, m))` | Count the smaller array |

The returned answer can contain up to `min(n, m)` elements.

## Implementation

```python
from collections import Counter

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        count = Counter(nums1)
        ans = []

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

        return ans
```

## Code Explanation

Use the smaller array for the frequency map:

```python
if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1
```

Count occurrences:

```python
count = Counter(nums1)
```

Scan the other array:

```python
for x in nums2:
```

If an unused matching occurrence exists:

```python
if count[x] > 0:
```

add it to the result:

```python
ans.append(x)
```

Then consume one occurrence:

```python
count[x] -= 1
```

## Sorting Alternative

If both arrays are already sorted, use two pointers.

```python
class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        nums1.sort()
        nums2.sort()

        i = 0
        j = 0
        ans = []

        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                ans.append(nums1[i])
                i += 1
                j += 1

        return ans
```

This takes `O(n log n + m log m)` time if sorting is needed, and `O(1)` extra space besides the output if sorting in place is allowed.

## Testing

Because order does not matter, sort results before comparison.

```python
def run_tests():
    s = Solution()

    assert sorted(s.intersect([1, 2, 2, 1], [2, 2])) == [2, 2]
    assert sorted(s.intersect([4, 9, 5], [9, 4, 9, 8, 4])) == [4, 9]

    assert sorted(s.intersect([1, 1, 1], [1, 1])) == [1, 1]
    assert sorted(s.intersect([1, 2, 3], [4, 5, 6])) == []
    assert sorted(s.intersect([0, 0, 1], [0, 0, 0])) == [0, 0]
    assert sorted(s.intersect([-1, -1, 2], [-1, 2, 2])) == [-1, 2]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,2,1]`, `[2,2]` | Duplicate intersection |
| `[4,9,5]`, `[9,4,9,8,4]` | Order does not matter |
| `[1,1,1]`, `[1,1]` | Uses minimum count |
| No overlap | Empty result |
| Zeros | Handles repeated zero values |
| Negative values | General integer behavior |