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

Function shape:

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

Examples

Example 1:

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:

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:

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

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:

O(n * m)

We can do better with hash sets.

Key Insight

A set gives two useful properties:

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:

set(nums1) & set(nums2)

means:

values that appear in both sets

Walkthrough

Use:

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

Convert to sets:

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

Take intersection:

{1, 2} & {2} = {2}

Return:

[2]

Now use:

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

Convert to sets:

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

Intersection:

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

Return either:

[4, 9]

or:

[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:

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

The returned list also stores the intersection.

Implementation

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:

set(nums1)

Convert nums2 into a set:

set(nums2)

Compute the common values:

set(nums1) & set(nums2)

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

list(...)

Alternative: Use One Set and Remove Matches

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

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.

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: