Common Element: Find All Elements Present in Every Array of a 2D List
Interview Experience
Problem
Given a list of n integer arrays,
return all elements that appear in every array. The result should be sorted in ascending order and contain no duplicates.
python
def common_elements(arrays: list[list[int]]) -> list[int]:
pass
Example:
arrays = [[3, 1, 2, 4], [1, 2, 5], [2, 1, 6]]
**output** -> [1, 2]
arrays = [[1, 2], [3, 4]]
**output** -> []
Approach
Convert the first array to a set, then intersect with each subsequent array. Final result sorted. O(n * m) time where m is average array length.
Follow-ups
1. What if n is 10,000 and each array has up to 1 million elements? Discuss memory trade-offs.
2. How do you handle duplicates within a single array -- does an element need to appear multiple times per array to be counted multiple times in the output?
3. Implement without using Python's built-in set.intersection.
4. Given the arrays arrive as a stream one at a time, maintain the running intersection incrementally.
Full Details
Problem
Given a list of n integer arrays,
return all elements that appear in every array. The result should be sorted in ascending order and contain no duplicates.
python
def common_elements(arrays: list[list[int]]) -> list[int]:
pass
Example:
arrays = [[3, 1, 2, 4], [1, 2, 5], [2, 1, 6]]
**output** -> [1, 2]
arrays = [[1, 2], [3, 4]]
**output** -> []
Approach
Convert the first array to a set, then intersect with each subsequent array. Final result sorted. O(n * m) time where m is average array length.
Follow-ups
1. What if n is 10,000 and each array has up to 1 million elements? Discuss memory trade-offs.
2. How do you handle duplicates within a single array -- does an element need to appear multiple times per array to be counted multiple times in the output?
3. Implement without using Python's built-in set.intersection.
4. Given the arrays arrive as a stream one at a time, maintain the running intersection incrementally.