350. Intersection of Two Arrays II

Problem¶

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

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 it interesting?¶

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

Python solution¶

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)
        res = []

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

        return res

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

Comment on 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