Intersection of Two Arrays II Solution

Problem

Given two integer arrays, return their intersection where each element appears in the result as many times as it appears in both arrays. The order of the output does not matter.

Example:

Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2, 2]
Explanation: The value 2 appears twice in both arrays, so it contributes two entries to the result.

Intuition

The key insight is that intersection with duplicates is a counting problem: the number of times value x belongs in the result equals min(freq(x, nums1), freq(x, nums2)). A frequency map on the smaller array lets us compute those minimums in a single linear pass through the larger array, replacing an O(n × m) search with O(n + m) arithmetic.

Approach 1 — Brute Force

For each element in nums1, scan nums2 for a match and remove it once found so the same occurrence cannot be reused.

Copy nums2 into a mutable list.
For each number in nums1, search the copy for a match.
If found, record the match and remove that one occurrence from the copy.
Return the result.

1from typing import List
2
3def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
4    nums2_copy = list(nums2)  # mutable copy so matched elements can be consumed
5    result = []
6    for num in nums1:
7        if num in nums2_copy:
8            result.append(num)
9            nums2_copy.remove(num)  # remove first occurrence to avoid reusing it
10    return result

Time: O(n × m) — each of the n elements in nums1 triggers a linear scan of up to m elements in nums2. Space: O(m) — the mutable copy of nums2.

Approach 2 — Hash Map (Optimal)

Build a frequency map from the smaller array, then consume counts as we scan the larger array.

Swap so that nums1 is the shorter array (minimises map memory).
Count each element's frequency in nums1.
Iterate through nums2; whenever an element still has remaining count, record it and decrement.
Return the result.

1from typing import List
2from collections import Counter
3
4def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
5    if len(nums1) > len(nums2):
6        nums1, nums2 = nums2, nums1  # always build the map from the smaller array
7    freq = Counter(nums1)
8    result = []
9    for num in nums2:
10        if freq[num] > 0:
11            result.append(num)
12            freq[num] -= 1  # consume one occurrence so it cannot match a second time
13    return result

Time: O(n + m) — one pass to build the map, one pass through the second array. Space: O(min(n, m)) — the frequency map holds at most min(n, m) distinct keys.

Approach 3 — Two Pointers (Sorted Arrays)

If both arrays are sorted (or sorting in-place is acceptable), two pointers need no extra hash map memory.

Sort both arrays.
Start a pointer at index 0 in each array.
If the pointed values are equal, record the match and advance both pointers.
Otherwise advance the pointer with the smaller value to seek a match.
Stop when either pointer passes its array's end.

1from typing import List
2
3def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
4    nums1.sort()
5    nums2.sort()
6    left, right = 0, 0
7    result = []
8    while left < len(nums1) and right < len(nums2):
9        if nums1[left] == nums2[right]:
10            result.append(nums1[left])
11            left += 1
12            right += 1
13        elif nums1[left] < nums2[right]:
14            left += 1   # nums1 value is smaller; advance to find a potential match
15        else:
16            right += 1  # nums2 value is smaller; advance to find a potential match
17    return result

Time: O(n log n + m log m) — dominated by sorting; the two-pointer scan is O(n + m). Space: O(1) extra — no hash map; only the output array is allocated.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n × m)	O(m)	Tiny inputs only; demonstrates the naive logic clearly
Hash Map	O(n + m)	O(min(n, m))	Default choice for unsorted or large inputs; fastest overall
Two Pointers	O(n log n + m log m)	O(1) extra	When memory is severely constrained or the inputs are already sorted

Common Mistakes

Using a plain set for the intersection: set(nums1) & set(nums2) discards duplicate counts, so [2, 2] ∩ [2, 2] wrongly returns [2] instead of [2, 2].
Forgetting to decrement the frequency count: Without freq[num] -= 1, a single occurrence in the first array will match every occurrence of that value in the second array, producing too many results.
Building the map from the larger array: The map should always track the smaller array; mapping a million-element array when the other has ten wastes memory proportional to the large array's distinct elements.
Treating list.remove(value) as O(1): In both Python and Java, removing by value requires a linear scan, making the brute-force approach O(n²) in the worst case — not O(n) as it might appear.
Advancing only one pointer on a mismatch in the two-pointer approach: Both pointers must ultimately advance past their respective ends; a logic error that advances neither on a mismatch causes an infinite loop.

Intersection of Two Arrays II — Solution