# LeetCode 349: Intersection of Two Arrays

## Problem Restatement

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

Return an array containing the intersection of the two arrays.

The intersection means the values that appear in both arrays.

Each value in the result must be unique, and the result can be returned in any order. The constraints allow values from `0` to `1000`, but a hash set solution works for general integers too.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integer arrays `nums1` and `nums2` |
| Output | Unique values that appear in both arrays |
| Duplicate handling | Each result value appears once |
| Order | Any order is accepted |

Function shape:

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

## Examples

Example 1:

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

The value `2` appears in both arrays.

Even though `2` appears more than once, the result contains it once.

Example 2:

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

Both `4` and `9` appear in both arrays.

The result may also be:

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

because output order does not matter.

## First Thought: Compare Every Pair

A direct solution is to check every value in `nums1` against every value in `nums2`.

If two values are equal, add that value to a result set.

```python
class Solution:
    def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
        result = set()

        for a in nums1:
            for b in nums2:
                if a == b:
                    result.add(a)

        return list(result)
```

This works because the result set removes duplicates.

But the nested loops are slow.

If `nums1` has length `n` and `nums2` has length `m`, this takes:

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

We can do better with hash sets.

## Key Insight

A set gives two useful properties:

| Property | Why it helps |
|---|---|
| Fast lookup | We can check whether a number exists in another array quickly |
| Uniqueness | Duplicates are removed automatically |

Convert one array into a set.

Then scan the other array.

If a value appears in the set, it belongs to the intersection.

To keep the result unique, store answers in another set, or use Python's set intersection operator directly.

## Algorithm

1. Convert `nums1` into a set.
2. Convert `nums2` into a set.
3. Return the intersection of the two sets.

In Python:

```python
set(nums1) & set(nums2)
```

means:

```text
values that appear in both sets
```

## Walkthrough

Use:

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

Convert to sets:

```text
set(nums1) = {1, 2}
set(nums2) = {2}
```

Take intersection:

```text
{1, 2} & {2} = {2}
```

Return:

```text
[2]
```

Now use:

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

Convert to sets:

```text
set(nums1) = {4, 5, 9}
set(nums2) = {4, 8, 9}
```

Intersection:

```text
{4, 5, 9} & {4, 8, 9} = {4, 9}
```

Return either:

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

or:

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

## Correctness

Converting `nums1` into a set preserves exactly the unique values that appear in `nums1`.

Converting `nums2` into a set preserves exactly the unique values that appear in `nums2`.

The set intersection operation returns exactly the values that appear in both sets.

Therefore, every returned value appears in both input arrays.

Also, every value that appears in both input arrays appears in both sets, so it is included in the intersection.

Because sets contain each value at most once, the result contains no duplicates.

Thus, the algorithm returns exactly the unique intersection of the two arrays.

## Complexity

Let:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + m)` | Build two sets and intersect them |
| Space | `O(n + m)` | Store unique values from both arrays |

The returned list also stores the intersection.

## Implementation

```python
class Solution:
    def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
        return list(set(nums1) & set(nums2))
```

## Code Explanation

Convert `nums1` into a set:

```python
set(nums1)
```

Convert `nums2` into a set:

```python
set(nums2)
```

Compute the common values:

```python
set(nums1) & set(nums2)
```

Convert back to a list because the required return type is an array:

```python
list(...)
```

## Alternative: Use One Set and Remove Matches

We can also use one set and remove values after adding them to the answer.

```python
class Solution:
    def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
        seen = set(nums1)
        ans = []

        for x in nums2:
            if x in seen:
                ans.append(x)
                seen.remove(x)

        return ans
```

This also guarantees uniqueness because once a value is added, it is removed from `seen`.

## Testing

Because order does not matter, compare sets in tests.

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

    assert set(s.intersection([1, 2, 2, 1], [2, 2])) == {2}
    assert set(s.intersection([4, 9, 5], [9, 4, 9, 8, 4])) == {4, 9}

    assert set(s.intersection([1, 2, 3], [4, 5, 6])) == set()
    assert set(s.intersection([1], [1])) == {1}
    assert set(s.intersection([1, 1, 1], [1, 1])) == {1}
    assert set(s.intersection([0, 1000, 5], [1000, 7, 0])) == {0, 1000}

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,2,1]`, `[2,2]` | Duplicate values in both arrays |
| `[4,9,5]`, `[9,4,9,8,4]` | Multiple common values |
| No overlap | Empty intersection |
| Single same value | Minimum common case |
| All duplicates | Result remains unique |
| Boundary-like values | Handles `0` and larger values |