Intersection of Multiple Arrays

Intersection of Multiple Arrays

1. What is this problem about?

The Intersection of Multiple Arrays interview question asks you to find all the integers that appear in every single sub-array within a given 2D list. The final result should be returned as a sorted list. Each sub-array contains unique integers.

2. Why is this asked in interviews?

Companies like Uber and Meta ask the Intersection of Multiple Arrays coding problem to test your knowledge of Hash Table interview patterns. It evaluations whether you can efficiently track frequencies across multiple groups. It’s a foundational problem for data aggregation and set operations.

3. Algorithmic pattern used

This problem follows the Frequency Counting pattern.

1. Count: Iterate through every element in every sub-array.
2. Map: Use a hash map (or a fixed-size array if values are small) to store how many times each number appears.
3. Filter: Since each number only appears at most once per sub-array, any number whose frequency is equal to the total number of sub-arrays must be present in all of them.
4. Sort: Collect these "perfect frequency" numbers and sort them.

4. Example explanation

Input: [[1, 2, 3], [4, 2, 1], [1, 2, 5]]

1. Frequency count:
   • 1: 3 times.
   • 2: 3 times.
   • 3: 1 time.
   • 4: 1 time.
   • 5: 1 time.
2. Filter: Only 1 and 2 have a count of 3.
3. Sorted Result: [1, 2].

5. Common mistakes candidates make

• Using Sets incorrectly: Manually performing set.intersection() repeatedly. While correct, frequency counting is often more performant and easier to reason about.
• Ignoring the sorting rule: Forgetting to sort the result before returning.
• Large value range: Assuming numbers are small (e.g., 1-1000) when they might be large, requiring a Hash Map instead of an array.

6. Interview preparation tip

Whenever you need to find elements common to $N$ groups, and elements are unique within groups, Counting is always the most efficient way. A count of $N$ is equivalent to a logical AND across all sets.