{x}
blog image

Intersection of Multiple Arrays

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 sorted in ascending order.

 

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.

Solution Explanation and Code

This problem asks to find the intersection of multiple arrays, meaning the numbers that appear in every single array. The solution utilizes a counting approach for efficiency.

Approach:

  1. Counting Occurrences: We use a hash map (or an array if we know the range of numbers beforehand, as in this case, numbers are between 1 and 1000) to store the frequency of each number across all input arrays. We iterate through each array and increment the count for each number encountered.

  2. Identifying Intersection: After counting, we iterate through the frequency map. Numbers that have a frequency equal to the number of input arrays are present in every array and thus belong to the intersection.

  3. Sorting and Returning: Finally, we collect these intersection numbers and sort them in ascending order before returning the result.

Time Complexity Analysis:

  • Counting: The nested loops iterate through all the numbers in the input nums. This takes O(N) time, where N is the total number of elements across all arrays.
  • Identifying Intersection: Iterating through the frequency map takes O(M) time, where M is the number of unique elements. In the worst case, M could be up to 1000 (all unique numbers between 1 and 1000). However, since it's a single loop through a fixed-size array (or hashmap with potentially less than 1000 entries), this is effectively O(1) if we use an array and O(M) for a hashmap.
  • Sorting: Sorting the intersection numbers takes O(K log K) time, where K is the size of the intersection. In the worst case, K could be 1000.

Therefore, the overall time complexity is dominated by the counting step, making it O(N). If using a hashmap, there is a potential O(M) for identifying the intersection, but M is bounded.

Space Complexity Analysis:

The space complexity is determined by the size of the frequency map (or array). Since the numbers are in the range [1, 1000], we can use a fixed-size array of size 1001 (or hashmap). The space required for storing the intersection is at most O(1000), which is constant. Therefore, the space complexity is O(1) if using an array, and O(M) if using a hashmap.

Code Implementation (Python, Java, C++, Go, TypeScript, PHP):

The provided code snippets in different programming languages above demonstrate the counting approach. They all follow the steps outlined above: counting, identifying intersection, and sorting. The Python, Java and C++ solutions utilize either an array (Solution 1) or a hashmap/dictionary (Solution 2) as needed. Go uses a map, while TypeScript uses an array initialized with fill(0). PHP uses a standard array to simulate the hashmap functionality. Each solution has a time complexity of O(N) and space complexity of O(1) for array solutions, and O(M) for hashmap based solutions.