Intersection of Two Arrays

Intersection of Two Arrays

1. What is this problem about?

The Intersection of Two Arrays interview question asks you to find the common elements between two arrays. Each element in the result must be unique, and you can return the result in any order.

2. Why is this asked in interviews?

This is a high-frequency question at Microsoft, Amazon, and Adobe. It evaluations your understanding of basic set theory and Hash Table interview patterns. It’s a test of choosing the most efficient way to check for membership.

3. Algorithmic pattern used

This problem follows the Hash Set pattern.

1. Set 1: Put all elements of the first array into a Hash Set. This handles uniqueness and provides $O(1)$ lookups.
2. Iterate: Loop through the second array.
3. Check: If an element from the second array exists in the set, add it to the result and remove it from the set (to ensure it’s not added to the result twice).
4. Alternative: If space is constrained but the arrays are sorted, use Two Pointers.

4. Example explanation

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

1. set1 = {1, 2}.
2. Iterate nums2:
   • Value 2 is in set1. Result: [2]. Remove 2 from set1.
   • Value 2 is NOT in set1 (already removed). Result: [2].

5. Common mistakes candidates make

• Including Duplicates: Returning [2, 2] instead of [2]. The result must contain unique values.
• Brute Force: Using nested loops to compare elements, resulting in $O(N \cdot M)$ complexity.
• Sorting unnecessarily: Calling sort() when a Hash Set could solve the problem in linear time.

6. Interview preparation tip

Be ready to discuss the trade-offs between a Hash Set ($O(N+M)$ time, $O(N)$ space) and Sorting + Two Pointers ($O(N \log N)$ time, $O(1)$ space). Interviewers love when you can provide the space-optimal solution if asked. This is a core Array interview pattern competency.