Find Common Elements Between Two Arrays

Find Common Elements Between Two Arrays

What is this problem about?

The Find Common Elements Between Two Arrays coding problem asks you to compare two integer arrays, nums1 and nums2. You need to find two values:

1. The number of indices $i$ in nums1 such that nums1[i] exists in nums2.
2. The number of indices $j$ in nums2 such that nums2[j] exists in nums1. This is a basic set membership and counting task.

Why is this asked in interviews?

This "Easy" problem is used by Meta and Amazon to evaluate basic data structure selection. it's a test of whether you recognize the Hash Table interview pattern. While nested loops would take $O(N imes M)$, using a Set reduces the lookup time to $O(1)$, resulting in an $O(N + M)$ solution. It evaluations your ability to optimize simple search operations.

Algorithmic pattern used

This problem uses Hash Sets for $O(1)$ membership testing.

1. Insert all unique elements of nums1 into a set set1.
2. Insert all unique elements of nums2 into a set set2.
3. Iterate through nums1: if nums1[i] is in set2, increment count1.
4. Iterate through nums2: if nums2[j] is in set1, increment count2.
5. Return [count1, count2].

Example explanation

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

1. set1 = {2, 3}, set2 = {1, 2}.
2. Check nums1:
   • 2 is in set2. (Count1 = 1)
   • 3 is not in set2.
   • 2 is in set2. (Count1 = 2)
3. Check nums2:
   • 1 is not in set1.
   • 2 is in set1. (Count2 = 1) Result: [2, 1].

Common mistakes candidates make

• Misinterpreting "indices": Counting unique values that are common instead of the total number of indices that satisfy the existence check.
• Brute force: Using nested loops for lookup, which is $O(N^2)$ and inefficient for large arrays.
• Forgetting the second count: Only solving the first half of the problem.

Interview preparation tip

Set membership is the most common use case for a Hash Set. If you need to check "Is this element in that collection?" multiple times, always build a Set from the collection first.