# Intersection of Multiple Arrays
**Difficulty:** EASY
[External](https://leetcode.com/problems/intersection-of-multiple-arrays)
Canonical: https://scaleengineer.com/dsa/problems/intersection-of-multiple-arrays
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
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**.

# Approaches
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.
```java
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;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- For each `candidate` in the first array `nums[0]`:
  - Set a boolean flag `isPresentInAll` to `true`.
  - For each subsequent array `nums[i]` (from `i=1` to `nums.length - 1`):
    - Linearly scan `nums[i]` to check for `candidate`.
    - If `candidate` is not found, set `isPresentInAll` to `false` and break the inner loop.
  - If `isPresentInAll` is still `true` after checking all arrays, add `candidate` to `result`.
- Sort the `result` list.
- Return `result`.

## Iterative Intersection with Hash Sets
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.
**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`).
**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.
### Explanation
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.
```java
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;
    }
}
```
### Algorithm
- Create a `HashSet`, `intersectionSet`, from the first array `nums[0]`.
- For each subsequent array `nums[i]` (from `i=1` to `nums.length - 1`):
  - Create a temporary `HashSet`, `currentSet`, from `nums[i]`.
  - Update `intersectionSet` to be the intersection of itself and `currentSet` (e.g., using `intersectionSet.retainAll(currentSet)`).
- Convert the final `intersectionSet` to a list.
- Sort the list.
- Return the sorted list.

## Frequency Counting with an Array
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.
**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.
**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.
### Explanation
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.
```java
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;
    }
}
```
### Algorithm
- Initialize a frequency array `counts` of size 1001 to all zeros.
- For each array `arr` in `nums`:
  - For each number `num` in `arr`:
    - Increment `counts[num]`.
- Initialize an empty list `result`.
- Let `N` be the total number of arrays (`nums.length`).
- Iterate `i` from 1 to 1000:
  - If `counts[i]` equals `N`, add `i` to `result`.
- Return `result`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 )]
```