Intersection of Two Arrays II

Intersection of Two Arrays II

1. What is this problem about?

The Intersection of Two Arrays II interview question asks you to find all the numbers that appear in both of two given arrays. Unlike the first version of this problem, you must include each element as many times as it appears in both arrays. For example, if '2' appears three times in the first array and twice in the second, '2' should appear twice in the final result.

2. Why is this asked in interviews?

This is a standard question at Google, Meta, and Amazon. It tests your ability to handle frequency management and choose the most appropriate data structure. It evaluation whether you understand the difference between a Set (unique elements) and a multiset or frequency map (tracking counts). It's a fundamental Hash Table interview pattern.

3. Algorithmic pattern used

This problem is typically solved using a Frequency Map.

1. Count: Iterate through the first array and store the frequency of each number in a hash map.
2. Intersect: Iterate through the second array. For each number:
   • If the number exists in the map and its count is $> 0$:
     • Add the number to the result list.
     • Decrement the count in the map.
3. Alternative: If the arrays are sorted, the Two Pointers pattern is more memory-efficient ($O(1)$ extra space).

4. Example explanation

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

1. Map from nums1: {4: 1, 9: 1, 5: 1}.
2. Iterate nums2:
   • 9: in map, count > 0. Result: [9]. Map: {4: 1, 9: 0, 5: 1}.
   • 4: in map, count > 0. Result: [9, 4]. Map: {4: 0, 9: 0, 5: 1}.
   • 9: in map, but count is 0. Skip.
   • 8: not in map. Skip. Result: [9, 4].

5. Common mistakes candidates make

• Using a Set: Using a simple Hash Set will only give you unique elements, missing the "include all occurrences" requirement.
• Sorting on large arrays: Sorting the arrays ($O(N \log N)$) when a Hash Map ($O(N)$) would be faster, unless memory is extremely limited.
• Not handling scale: Failing to discuss what happens if one array is much smaller than the other (you should hash the smaller one) or if the arrays are stored on disk (external sort).

6. Interview preparation tip

Always clarify the requirements: "Do I need unique elements or all duplicates?" If duplicates matter, think Hash Map with Counts. This is a core Array interview pattern for data reconciliation tasks.