LeetCode 350 - Intersection of Two Arrays II

LeetCode Problem 350

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem asks us to find the intersection of two integer arrays, but with an important detail: duplicates matter. If a number appears multiple times in both arrays, it must appear in the result as many times as it appears in both.

For example, if 2 appears twice in nums1 and three times in nums2, then the result should contain 2 exactly twice. The number of occurrences in the intersection is determined by the minimum frequency across the two arrays.

The input consists of two arrays of integers:

• nums1
• nums2

The output is another array containing all common elements, including duplicates. The order of the output does not matter.

The constraints are relatively small:

• Each array length is between 1 and 1000
• Each value is between 0 and 1000

These constraints tell us several important things:

• An O(n * m) brute-force solution is technically feasible because the arrays are small
• However, the problem is designed to test knowledge of hash tables, sorting, and two-pointer techniques
• Since values are bounded, frequency counting is particularly natural

There are several edge cases worth thinking about early:

• Arrays with no common elements, the result should be empty
• Arrays where every element is identical
• Arrays with heavy duplication
• Arrays of very different sizes
• Arrays already sorted, which enables a two-pointer optimization
• One array being much smaller than the other, which can influence which data structure is preferable

The problem guarantees valid integer arrays and does not require preserving order, which simplifies the implementation.

Approaches

Brute Force Approach

The brute-force solution compares every element in nums1 against every element in nums2. To avoid reusing the same element multiple times, we also need a mechanism to mark elements in nums2 as already matched.

One way to implement this is:

• Iterate through each element in nums1

• For each element, scan through nums2

• If a matching unused element is found:

• Add it to the result

• Mark that position as used

• Stop searching for that element

This approach is correct because every valid match is explicitly found and consumed exactly once.

However, it is inefficient because every element may require scanning the entire second array. The time complexity becomes O(n * m).

Optimal Approach Using a Hash Map

The key insight is that this problem is fundamentally about frequencies.

Instead of repeatedly searching for matches, we can count how many times each number appears in one array. Then, while iterating through the second array, we check whether that number still has remaining unused occurrences.

A hash map works perfectly here because:

• It provides average O(1) lookup
• It naturally stores frequencies
• It allows us to decrement counts as matches are used

The algorithm becomes:

1. Count frequencies of all numbers in nums1
2. Traverse nums2
3. If the current number exists in the frequency map with count greater than zero:

• Add it to the result
• Decrease its count

This avoids repeated scanning and reduces the complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(m)	Compares every pair and tracks used elements
Optimal	O(n + m)	O(min(n, m))	Uses a hash map to count frequencies efficiently

Algorithm Walkthrough

Optimal Hash Map Algorithm

1. Create a frequency map for one of the arrays.

We choose one array, typically the smaller one for memory efficiency, and count how many times each number appears. The key is the number itself, and the value is its frequency.

Example:

nums1 = [1,2,2,1]

frequency_map = {
    1: 2,
    2: 2
}

2. Initialize an empty result array.

This array will store the intersection elements as we discover valid matches. 3. Traverse the second array.

For each number in nums2, check whether it exists in the frequency map and whether its remaining count is greater than zero. 4. If a valid count exists, add the number to the result.

This means the number still has unmatched occurrences available from the first array. 5. Decrement the frequency count.

After using one occurrence, reduce its count so it cannot be reused incorrectly. 6. Continue until all elements are processed.

By the end, the result contains exactly the shared elements with correct multiplicities.

Why it works

The algorithm maintains the invariant that the frequency map always represents how many unused occurrences of each number remain from the first array.

Whenever we encounter a number in the second array:

• If the count is positive, a valid unmatched occurrence exists
• After using it, we decrement the count
• Once the count reaches zero, no further copies may be added

This guarantees that each element appears in the result exactly min(count_in_nums1, count_in_nums2) times.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Always build the frequency map from the smaller array
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        frequency = Counter(nums1)
        result = []

        for num in nums2:
            if frequency[num] > 0:
                result.append(num)
                frequency[num] -= 1

        return result

The implementation begins by ensuring the smaller array is used for the frequency map. This is a small optimization that reduces memory usage when the arrays differ significantly in size.

Counter from Python's collections module automatically builds the frequency map. Each key is a number and each value is the number of occurrences.

The algorithm then iterates through nums2. For every number:

• If its frequency is still positive, it means an unused matching occurrence exists
• The number is appended to the result
• The count is decremented to mark one occurrence as consumed

The final result array is returned after all elements are processed.

Go Solution

func intersect(nums1 []int, nums2 []int) []int {
    // Use the smaller array for the frequency map
    if len(nums1) > len(nums2) {
        nums1, nums2 = nums2, nums1
    }

    frequency := make(map[int]int)

    for _, num := range nums1 {
        frequency[num]++
    }

    result := []int{}

    for _, num := range nums2 {
        if frequency[num] > 0 {
            result = append(result, num)
            frequency[num]--
        }
    }

    return result
}

The Go implementation follows the same logic as the Python version.

The main difference is that Go does not provide a built-in Counter type, so we manually construct a map[int]int to store frequencies.

Slices in Go naturally support dynamic appending through append, making them suitable for building the result incrementally.

There are no integer overflow concerns here because the constraints are very small.

An empty slice is returned automatically when no intersection exists, which matches LeetCode expectations.

Worked Examples

Example 1

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

First, build the frequency map from nums2 because it is smaller.

Number	Frequency
2	2

Now process nums1.

Current Number	Frequency Before	Action	Result	Frequency After
1	0	Skip	[]	0
2	2	Add to result	[2]	1
2	1	Add to result	[2,2]	0
1	0	Skip	[2,2]	0

Final result:

[2,2]

Example 2

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

Build the frequency map from nums1.

Number	Frequency
4	1
9	1
5	1

Process nums2.

Current Number	Frequency Before	Action	Result	Frequency After
9	1	Add	[9]	0
4	1	Add	[9,4]	0
9	0	Skip	[9,4]	0
8	0	Skip	[9,4]	0
4	0	Skip	[9,4]	0

Final result:

[9,4]

Any ordering such as [4,9] is also valid.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each array is traversed once
Space	O(min(n, m))	Frequency map stores counts for the smaller array

The time complexity is linear because every element from both arrays is processed exactly once.

The space complexity depends on the number of distinct elements stored in the frequency map. Since we build the map from the smaller array, the auxiliary space is bounded by O(min(n, m)).

Test Cases

from typing import List

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        from collections import Counter

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

        frequency = Counter(nums1)
        result = []

        for num in nums2:
            if frequency[num] > 0:
                result.append(num)
                frequency[num] -= 1

        return result

solution = Solution()

# Provided example with duplicates
assert sorted(solution.intersect([1,2,2,1], [2,2])) == [2,2]

# Provided example with unordered output
assert sorted(solution.intersect([4,9,5], [9,4,9,8,4])) == [4,9]

# No intersection
assert solution.intersect([1,2,3], [4,5,6]) == []

# Identical arrays
assert sorted(solution.intersect([1,1,1], [1,1,1])) == [1,1,1]

# One array significantly larger
assert sorted(solution.intersect([1], [1,1,1,1])) == [1]

# Partial overlap with duplicates
assert sorted(solution.intersect([1,2,2,3], [2,2,2])) == [2,2]

# Single element arrays
assert solution.intersect([5], [5]) == [5]

# Single element with no match
assert solution.intersect([5], [6]) == []

# Large duplicate counts
assert sorted(solution.intersect([0,0,0,0], [0,0])) == [0,0]

# Different ordering
assert sorted(solution.intersect([3,1,2], [2,3])) == [2,3]

Test	Why
[1,2,2,1] and [2,2]	Verifies duplicate handling
[4,9,5] and [9,4,9,8,4]	Verifies unordered intersection
[1,2,3] and [4,5,6]	Tests empty intersection
[1,1,1] and [1,1,1]	Tests all elements matching
[1] and [1,1,1,1]	Tests size imbalance
[1,2,2,3] and [2,2,2]	Ensures minimum frequency logic
[5] and [5]	Smallest valid matching input
[5] and [6]	Smallest valid non-matching input
[0,0,0,0] and [0,0]	Tests repeated zero values
[3,1,2] and [2,3]	Verifies ordering independence

Edge Cases

Arrays With No Common Elements

A common source of bugs is accidentally including unmatched values due to incorrect default behavior in the frequency map.

Example:

nums1 = [1,2,3]
nums2 = [4,5,6]

The implementation correctly handles this because it only appends a number when its frequency count is greater than zero. Since none of these values exist in the map, the result remains empty.

Heavy Duplicate Counts

Duplicates are the core challenge of this problem.

Example:

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

A naive set-based solution would incorrectly return only [2]. Our implementation tracks exact frequencies and decrements counts after each match, ensuring the result becomes [2,2].

Arrays of Very Different Sizes

When one array is much larger than the other, memory usage becomes important.

Example:

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

The implementation optimizes for this by always building the frequency map from the smaller array. This minimizes auxiliary space while maintaining linear time complexity.

Already Sorted Arrays

If the arrays are already sorted, a two-pointer solution can avoid extra hash map memory entirely.

Example:

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

Using two pointers:

• Compare current elements
• Advance the smaller pointer
• Record matches when equal

This achieves O(n + m) time with O(1) extra space, aside from the output array.