Intersection of Multiple Arrays - Solution & Explanation

Problem Overview: You receive a list of integer arrays. The task is to return all numbers that appear in every array. The final result must be sorted in ascending order. This is essentially computing the intersection across multiple arrays rather than just two.

Approach 1: Hash Map Counting (O(N) time, O(U) space)

This approach counts how many arrays contain each value. Iterate through every number in every array and maintain a frequency map using a hash table. The key insight is that a value belongs in the final intersection only if its count equals the number of arrays. After counting, iterate through the map and collect numbers whose frequency equals nums.length. Since the output must be sorted, apply a final sort step on the result list.

Hash table lookups and updates run in constant time on average, making the overall counting phase linear with respect to the total number of elements across all arrays. This approach works well for the general case and handles duplicate values naturally because the counting logic focuses on array presence rather than position.

Relevant concepts: hash table, counting, and array.

Approach 2: Set Intersection (O(N) time, O(U) space)

Another clean strategy uses set intersections. Convert the first array into a set, then iteratively intersect it with sets created from each remaining array. Each intersection keeps only elements that exist in both sets. After processing all arrays, the resulting set contains values common to every array.

This method works because set intersection removes any element missing from even one array. Most languages provide optimized set operations that run in roughly linear time relative to the number of elements involved. Once the final set is computed, convert it into a list and sort it to satisfy the problem's ordering requirement.

This approach is often shorter to implement and easier to reason about compared with manual counting. It relies on standard hash table backed sets and simple intersection operations. Sorting is still required at the end, so the final step uses typical sorting algorithms.

Recommended for interviews: Interviewers typically expect the hash map counting solution. It demonstrates understanding of frequency tracking and how to aggregate information across multiple arrays. The set intersection approach is equally valid and often more concise, but explaining the counting logic clearly shows strong command of hash-based techniques used in many array problems.