Intersection of Multiple Arrays
EasyPrompt
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 <= 10001 <= sum(nums[i].length) <= 10001 <= nums[i][j] <= 1000- All the values of
nums[i]are unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each element of the first array and checks if it is present in all the other subsequent arrays. If an element is found in every array, it's added to the result list.
Algorithm
- Initialize an empty list
result. - For each
candidatein the first arraynums[0]:- Set a boolean flag
isPresentInAlltotrue. - For each subsequent array
nums[i](fromi=1tonums.length - 1):- Linearly scan
nums[i]to check forcandidate. - If
candidateis not found, setisPresentInAlltofalseand break the inner loop.
- Linearly scan
- If
isPresentInAllis stilltrueafter checking all arrays, addcandidatetoresult.
- Set a boolean flag
- Sort the
resultlist. - Return
result.
Walkthrough
We start by considering the first array nums[0] as a base for potential candidates for the intersection.
We iterate through each number candidate in nums[0].
For each candidate, we then check its presence in all the other arrays from nums[1] to nums[nums.length - 1].
A flag, say isPresentInAll, is used to track if the candidate is found in every array.
To check if candidate is in nums[i], we perform a linear scan through nums[i]. If it's not found, we set the flag to false and can immediately stop checking for this candidate in further arrays.
If the flag remains true after checking all arrays, the candidate is added to our result list.
Finally, the result list is sorted in ascending order as required.
import java.util.*; class Solution { public List<Integer> intersection(int[][] nums) { if (nums == null || nums.length == 0) { return new ArrayList<>(); } List<Integer> result = new ArrayList<>(); // Iterate through each number in the first array for (int candidate : nums[0]) { boolean isPresentInAll = true; // Check against all other arrays for (int i = 1; i < nums.length; i++) { boolean foundInCurrentArray = false; // Linear scan to find the candidate in the current array for (int num : nums[i]) { if (num == candidate) { foundInCurrentArray = true; break; } } if (!foundInCurrentArray) { isPresentInAll = false; break; } } if (isPresentInAll) { result.add(candidate); } } Collections.sort(result); return result; }}Complexity
Time
O(L_0 * S), where `L_0` is the length of the first array and `S` is the total number of elements in `nums`. For each of the `L_0` elements, we might scan through almost all other `S - L_0` elements. Sorting adds an additional `O(k log k)` complexity.
Space
O(k), where `k` is the number of elements in the intersection. This space is used for the result list. In the worst case, `k` can be up to the length of the smallest array.
Trade-offs
Pros
Simple to understand and implement without complex data structures.
Cons
Highly inefficient, especially if the arrays are large.
The time complexity is poor due to multiple nested loops and repeated linear scans.
This method improves upon the brute-force approach by using hash sets for efficient lookups. It starts with a set of elements from the first array and iteratively finds the intersection with each subsequent array.
Algorithm
- Create a
HashSet,intersectionSet, from the first arraynums[0]. - For each subsequent array
nums[i](fromi=1tonums.length - 1):- Create a temporary
HashSet,currentSet, fromnums[i]. - Update
intersectionSetto be the intersection of itself andcurrentSet(e.g., usingintersectionSet.retainAll(currentSet)).
- Create a temporary
- Convert the final
intersectionSetto a list. - Sort the list.
- Return the sorted list.
Walkthrough
The core idea is to compute the intersection iteratively. The intersection of (A, B, C) is (A ∩ B) ∩ C.
We first create a HashSet from the elements of the first array, nums[0]. This set, let's call it intersectionSet, will store the common elements found so far.
Then, we iterate through the remaining arrays, from nums[1] to the end.
In each iteration i, we create a temporary HashSet for the current array nums[i].
We then update intersectionSet by retaining only the elements that are also present in the temporary set of nums[i]. The retainAll method of HashSet is perfect for this, as it performs an intersection operation in-place.
After the loop finishes, intersectionSet contains all numbers that are present in every single array.
Finally, we convert the intersectionSet into a list, sort it, and return it.
import java.util.*;import java.util.stream.Collectors; class Solution { public List<Integer> intersection(int[][] nums) { if (nums == null || nums.length == 0) { return new ArrayList<>(); } Set<Integer> intersectionSet = new HashSet<>(); for (int num : nums[0]) { intersectionSet.add(num); } for (int i = 1; i < nums.length; i++) { Set<Integer> currentSet = new HashSet<>(); for (int num : nums[i]) { currentSet.add(num); } // Keep only the elements that are in both sets intersectionSet.retainAll(currentSet); } List<Integer> result = new ArrayList<>(intersectionSet); Collections.sort(result); return result; }}Complexity
Time
O(S + k log k), where `S` is the total number of elements in `nums` and `k` is the size of the intersection. Populating all the sets and performing intersections takes `O(S)` time in total. Sorting the final result of size `k` takes `O(k log k)`.
Space
O(M), where `M` is the maximum length of any single array in `nums`. We need space for the main `intersectionSet` (at most the size of `nums[0]`) and the `currentSet` for each iteration (at most size `M`).
Trade-offs
Pros
Much more efficient than brute force due to O(1) average time complexity for set lookups and insertions.
Cons
Requires extra space for the hash sets.
The final sorting step adds to the complexity.
Hash set operations have a higher constant factor overhead compared to array lookups.
This is the most efficient approach given the constraints on the input values. It uses a frequency array to count the occurrences of each number across all the arrays. A number is in the intersection if its count equals the total number of arrays.
Algorithm
- Initialize a frequency array
countsof size 1001 to all zeros. - For each array
arrinnums:- For each number
numinarr:- Increment
counts[num].
- Increment
- For each number
- Initialize an empty list
result. - Let
Nbe the total number of arrays (nums.length). - Iterate
ifrom 1 to 1000:- If
counts[i]equalsN, additoresult.
- If
- Return
result.
Walkthrough
The problem states that all numbers are positive integers between 1 and 1000. This limited range makes a frequency counting array (or a direct addressing table) an ideal data structure.
We initialize an integer array, counts, of size 1001, with all values set to 0. The index of this array will correspond to a number, and the value at that index will store how many of the input arrays contain this number.
We then iterate through each array nums[i]. For each number num within nums[i], we increment counts[num]. Since the problem guarantees that numbers within a single array nums[i] are distinct, we don't have to worry about overcounting within the same array.
After processing all the numbers from all arrays, the counts array is fully populated.
We then create an empty list for our result. We iterate from 1 to 1000 (the possible range of numbers). For each number j, we check if counts[j] is equal to nums.length.
If counts[j] == nums.length, it means the number j was present in every single array, so we add it to our result list.
Because we iterate from 1 to 1000, the numbers are added to the result list in ascending order automatically. No final sorting step is needed.
import java.util.*; class Solution { public List<Integer> intersection(int[][] nums) { int[] counts = new int[1001]; for (int[] arr : nums) { for (int num : arr) { counts[num]++; } } List<Integer> result = new ArrayList<>(); int n = nums.length; for (int i = 1; i < counts.length; i++) { if (counts[i] == n) { result.add(i); } } // The result is already sorted return result; }}Complexity
Time
O(S + V), where `S` is the total number of elements in `nums` and `V` is the maximum possible value of an element (1000). `O(S)` to populate the counts array and `O(V)` to scan it for the result.
Space
O(V), for the frequency array, where `V` is the maximum possible value of an element (1000). In this case, it's `O(1001)` which is effectively constant space.
Trade-offs
Pros
Very efficient in both time and space due to direct addressing.
Avoids the overhead of hashing.
Produces a sorted result naturally, eliminating the need for a final sort.
Cons
This approach is only feasible because the range of input values is small and known beforehand.
It would be inefficient in terms of space for a large or unbounded range of numbers.
Solutions
Solution
class Solution {public List<Integer> intersection(int[][] nums) { int[] cnt = new int[1001]; for (var arr : nums) { for (int x : arr) { ++cnt[x]; } } List<Integer> ans = new ArrayList<>(); for (int x = 0; x < 1001; ++x) { if (cnt[x] == nums.length) { ans.add(x); } } return ans; }}class Solution {public: vector<int> intersection(vector<vector<int>> &nums) { int cnt[1001]{}; for (auto &arr : nums) { for (int &x : arr) { ++cnt[x]; } } vector<int> ans; for (int x = 0; x < 1001; ++x) { if (cnt[x] == nums.size()) { ans.push_back(x); } } return ans; }};class Solution : def intersection ( self , nums : List [ List [ int ]]) -> List [ int ]: cnt = [ 0 ] * 1001 for arr in nums : for x in arr : cnt [ x ] += 1 return [ x for x , v in enumerate ( cnt ) if v == len ( nums )]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.