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:

min(a, b)

times in the answer.

The result may be returned in any order.

Input and Output

Function shape:

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

Examples

Example 1:

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:

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:

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

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:

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

Count the smaller array:

nums2 -> {2: 2}

Scan nums1.

Read 1.

count[1] = 0

Skip it.

Read 2.

count[2] = 2

Append 2, then decrease:

count[2] = 1
answer = [2]

Read another 2.

Append again:

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

Read 1.

Skip it.

Final answer:

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

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

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

Implementation

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:

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

Count occurrences:

count = Counter(nums1)

Scan the other array:

for x in nums2:

If an unused matching occurrence exists:

if count[x] > 0:

add it to the result:

ans.append(x)

Then consume one occurrence:

count[x] -= 1

Sorting Alternative

If both arrays are already sorted, use two pointers.

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.

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: