350. Intersection of Two Arrays II

Reformulated question¶

Return the multiset intersection of nums1 and nums2: keep each value exactly min(count in nums1, count in nums2) times, in any order.

Compact example:

nums1 = [1,2,2,1], nums2 = [2,2] -> [2,2]
# 2 appears twice in both, so keep it twice

Key trick¶

Count occurrences in one array, then consume matches while scanning the other.

Counter(nums1) gives available copies.
For each value in nums2, add it only if its remaining count is positive.

Trap¶

Using set intersection, which loses duplicates.
Forgetting output order is irrelevant, so tests should compare multisets, not raw list order.
Not decrementing counts after using a match.

Why is this question interesting?¶

It is a simple frequency-count problem that tests whether you notice this is a multiset intersection, not a set intersection.

Solve the problem with idiomatic Python¶

from collections import Counter

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        # Count one side, then consume matches from the other side.
        counts = Counter(nums1)
        out = []

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

        return out

Exact-library solution with same idea:

from collections import Counter

class SolutionCounterMath:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        # Counter intersection keeps min counts for each key.
        return list((Counter(nums1) & Counter(nums2)).elements())

Pytest test¶

@pytest.mark.parametrize(
    ("nums1", "nums2", "expected"),
    [
        ([1, 2, 2, 1], [2, 2], [2, 2]),
        ([4, 9, 5], [9, 4, 9, 8, 4], [4, 9]),
        ([1, 2, 2, 1], [3, 4], []),
        ([1], [1], [1]),
        ([2, 2, 2], [2, 2], [2, 2]),
        ([1, 1, 2, 3], [1, 1, 1, 3], [1, 1, 3]),
        ([0, 0, 0], [0, 0, 1], [0, 0]),
    ],
)
def test_intersect(nums1, nums2, expected):
    assert sorted(Solution().intersect(nums1, nums2)) == sorted(expected)

Comment my solution¶

Your main solution is correct and idiomatic.

Good:
Uses Counter.
Consumes counts correctly.
Removes keys at zero, which is optional but fine.
Small improvements:
if nums1_counts[n2] > 0: is simpler than checking membership then popping.
Your tests should ignore order with sorted(...) or Counter(...).
You defined test_intersect twice, so the second one overrides the first in Python.
SolutionSorted:
Correct two-pointer solution for already sorted arrays.
Nice answer to the follow-up, but separate from the main unsorted problem.

from collections import Counter
import pytest

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        nums1_counts = Counter(nums1)
        intersection = []
        for n2 in nums2:
            if n2 in nums1_counts:
                intersection.append(n2)
                nums1_counts[n2] -= 1
                if nums1_counts[n2] == 0:
                    nums1_counts.pop(n2)
        return intersection

class SolutionSorted:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        # we assume nums1 and nums2 are sorted
        i, j = 0, 0
        intersection = []
        while (i < len(nums1) and j < len(nums2)):
            if nums1[i] == nums2[j]:
                intersection.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return intersection


@pytest.mark.parametrize(
    ("nums1", "nums2", "expected"),
    [
        ([1,2,2,1], [2,2], [2,2]),
        # we should write the test differently to take into
        # account the output order doesn't matter to make it
        # independent from the implementation.
        ([4,9,5], [9,4,9,8,4], [9,4]), # [4,9] accepted
        ([1,2,2,1], [3, 4], [])
    ]
)
def test_intersect(nums1, nums2, expected):

    assert Solution().intersect(nums1, nums2) == expected

@pytest.mark.parametrize(
    ("nums1", "nums2", "expected"),
    [
        ([1,2,2], [2,2], [2,2]),
        ([4,5,9], [4,8,9], [4,9]), # [9,4] accepted
        ([1,2,2,3], [4, 5], []),
        ([1,2,2,2,5,8,8,9], [2,2,7,8,8,8,10,12,13,14], [2,2,8,8]),
    ]
)
def test_intersect_sorted(nums1, nums2, expected):

    assert SolutionSorted().intersect(nums1, nums2) == expected

Code¶

from collections import Counter
import pytest


class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        # Count one array, then consume matches from the other.
        counts = Counter(nums1)
        out = []

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

        return out


class SolutionCounterMath:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        # Exact-library solution: multiset intersection.
        return list((Counter(nums1) & Counter(nums2)).elements())


class SolutionSorted:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        # Follow-up: if both arrays are already sorted, use two pointers.
        i = 0
        j = 0
        out = []

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

        return out


@pytest.mark.parametrize(
    ("nums1", "nums2", "expected"),
    [
        ([1, 2, 2, 1], [2, 2], [2, 2]),
        ([4, 9, 5], [9, 4, 9, 8, 4], [4, 9]),
        ([1, 2, 2, 1], [3, 4], []),
        ([1], [1], [1]),
        ([2, 2, 2], [2, 2], [2, 2]),
        ([1, 1, 2, 3], [1, 1, 1, 3], [1, 1, 3]),
        ([0, 0, 0], [0, 0, 1], [0, 0]),
    ],
)
def test_intersect(nums1, nums2, expected):
    # Order does not matter, so compare sorted outputs.
    assert sorted(Solution().intersect(nums1, nums2)) == sorted(expected)


# Compact examples to run interactively:
Solution().intersect([1, 2, 2, 1], [2, 2])
SolutionCounterMath().intersect([4, 9, 5], [9, 4, 9, 8, 4])
SolutionSorted().intersect([1, 2, 2, 2, 5, 8, 8, 9], [2, 2, 7, 8, 8, 8, 10])