Intersection of Multiple Arrays

Difficulty: Easy | Acceptance: 68.70% | Paid: No Topics: Array, Hash Table, Sorting, Counting

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array of nums. You may return the answer in any order.

• Examples
• Constraints
• Hash Map Frequency Counting
• Set Intersection
• Sorting and Binary Search

Examples

Example 1

Input:

nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]

Output:

[3,4]

Explanation: The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2

Input:

nums = [[1,2,3],[4,5,6]]

Output:

[]

Explanation: There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

Constraints

1 <= nums.length <= 1000
1 <= sum(nums[i].length) <= 1000
1 <= nums[i][j] <= 1000
All the values of nums[i] are unique.

Hash Map Frequency Counting

Intuition We can count the frequency of every number across all subarrays. Since each subarray contains distinct integers, a number that appears in the intersection must appear exactly once in every subarray. Therefore, its total frequency across the entire 2D array must equal the number of subarrays.

Steps

• Initialize a hash map to store the frequency of each number.
• Iterate through each number in every subarray of nums.
• Increment the count for each number in the hash map.
• Iterate through the hash map and collect all keys where the value is equal to nums.length.

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        from collections import Counter
        freq = Counter()
        
        for arr in nums:
            freq.update(arr)
            
        n = len(nums)
        return [num for num, count in freq.items() if count == n]

Complexity

• Time: O(N), where N is the total number of elements across all arrays.
• Space: O(N), to store the frequency map.
• Notes: This is the most straightforward approach and handles unsorted data efficiently.

Set Intersection

Intuition We can iteratively compute the intersection of sets. Start by converting the first array into a set. Then, for every subsequent array, convert it to a set and update our result set to keep only the elements common to both.

Steps

• Initialize a result set with the elements of the first array.
• Iterate through the remaining arrays.
• For each array, convert it to a set and update the result set to retain only elements found in the current array’s set.
• Convert the final result set back to a list.

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        if not nums:
            return []
        
        common_set = set(nums[0])
        
        for arr in nums[1:]:
            common_set.intersection_update(arr)
            
        return sorted(list(common_set))

Complexity

• Time: O(N), where N is the total number of elements. Set operations (add, contains) are O(1) on average.
• Space: O(N), to store the sets.
• Notes: This approach is very readable and leverages built-in set operations effectively.

Sorting and Binary Search

Intuition If we sort all the arrays, we can pick the smallest array (or the first one) and check if each of its elements exists in all other arrays using binary search. This reduces the lookup time compared to linear search, though we pay the cost of sorting first.

Steps

• Sort every array in nums.
• Iterate through each element of the first array.
• For each element, perform a binary search in all other arrays.
• If the element is found in every array, add it to the result.

import bisect

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        for arr in nums:
            arr.sort()
            
        result = []
        for num in nums[0]:
            found_in_all = True
            for i in range(1, len(nums)):
                idx = bisect.bisect_left(nums[i], num)
                if idx == len(nums[i]) or nums[i][idx] != num:
                    found_in_all = False
                    break
            if found_in_all:
                result.append(num)
                
        return result

Complexity

• Time: O(N log N) due to sorting the arrays.
• Space: O(1) auxiliary space (excluding the space for the output and the sorting stack, which is usually O(log N) for Timsort).
• Notes: This approach is useful if the arrays are already sorted or if memory is extremely constrained (avoiding hash maps), though it is generally slower than the hash map approach for this problem.