# Intersection of Two Arrays II
**Difficulty:** EASY
[External](https://leetcode.com/problems/intersection-of-two-arrays-ii)
Canonical: https://scaleengineer.com/dsa/problems/intersection-of-two-arrays-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Yandex](https://scaleengineer.com/companies/yandex)
---
## Problem
Given two integer arrays `nums1` and `nums2`, return _an array of their intersection_. Each element in the result must appear as many times as it shows in both arrays and you may return the result in **any order**.

**Example 1:**

**Input:** nums1 = [1,2,2,1], nums2 = [2,2]
**Output:** [2,2]

**Example 2:**

**Input:** nums1 = [4,9,5], nums2 = [9,4,9,8,4]
**Output:** [4,9]
**Explanation:** [9,4] is also accepted.

**Constraints:**

* `1 <= nums1.length, nums2.length <= 1000`
* `0 <= nums1[i], nums2[i] <= 1000`

**Follow up:**

* What if the given array is already sorted? How would you optimize your algorithm?
* What if `nums1`'s size is small compared to `nums2`'s size? Which algorithm is better?
* What if elements of `nums2` are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

# Approaches
## Brute Force with Nested Loops
This approach uses nested loops to compare every element of the first array with every element of the second array. To handle duplicates correctly, once an element from the second array is matched, it's marked as used to prevent it from being matched again.
**Time:** O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. In the worst case, for each element in `nums1`, we might have to scan the entire `nums2`. · **Space:** O(m) to store the `used` boolean array, where `m` is the length of `nums2`. The space for the result list is additional, which can be up to O(min(n, m)).
**Pros:** Simple to conceptualize and implement.; Doesn't require complex data structures beyond a list and a boolean array.
**Cons:** Highly inefficient, with a quadratic time complexity.; Likely to result in a 'Time Limit Exceeded' error on most platforms for larger inputs.
### Explanation
The brute-force method involves a straightforward comparison. We take each element from the first array, `nums1`, and search for a match in the second array, `nums2`. To correctly handle the frequency of elements, we need to ensure that once an element from `nums2` is part of a match, it cannot be used again. A boolean array, `used`, of the same size as `nums2` can track this. When a match is found at `nums2[j]`, we add the element to our result list and set `used[j]` to `true`. We then break the inner loop to avoid matching the same `nums1` element with other identical elements in `nums2`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> intersection = new ArrayList<>();
        boolean[] used = new boolean[nums2.length];
        
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j] && !used[j]) {
                    intersection.add(nums1[i]);
                    used[j] = true;
                    break; // Move to the next element in nums1
                }
            }
        }
        
        // Convert List to array
        int[] result = new int[intersection.size()];
        for (int i = 0; i < intersection.size(); i++) {
            result[i] = intersection.get(i);
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `intersection` to store the result.
- Create a boolean array `used` of the same size as `nums2`, initialized to `false`.
- Iterate through each element `num1` in `nums1`.
- For each `num1`, iterate through `nums2` with an index `j`.
- If `num1` equals `nums2[j]` and `used[j]` is `false`, it's a match.
- Add `num1` to the `intersection` list.
- Set `used[j]` to `true` to mark this element as used.
- Break the inner loop and move to the next element in `nums1`.
- After the loops complete, convert the `intersection` list to an array and return it.

## Sorting with Two Pointers
This approach first sorts both arrays. Then, it uses two pointers to iterate through the sorted arrays simultaneously. By comparing the elements at the pointers, we can find the common elements efficiently in a single pass after sorting.
**Time:** O(n log n + m log m), where `n` and `m` are the lengths of the arrays. The dominant operation is sorting. The two-pointer scan takes linear time, O(n + m). · **Space:** O(log n + log m) to O(n + m), depending on the implementation of the sorting algorithm used by the language's standard library. This does not include the space for the result list, which is O(min(n, m)).
**Pros:** Very efficient if the arrays are already sorted (O(n + m) time).; Space-efficient, especially if an in-place sort with logarithmic space is used.
**Cons:** The sorting step can be costly if the arrays are large and unsorted.; Modifies the original arrays if sorted in-place, which might not be desirable.
### Explanation
A more efficient way to solve the problem is to first sort both arrays. Once sorted, we can use a two-pointer technique. We initialize one pointer at the beginning of each array. We then compare the elements at the two pointers:
- If the element in `nums1` is smaller, we advance the pointer for `nums1` because we need to find a larger value to match the current element in `nums2`.
- If the element in `nums2` is smaller, we advance the pointer for `nums2` for the same reason.
- If the elements are equal, we have found a common element. We add it to our result list and advance both pointers to look for the next potential match.
This process continues until one of the pointers goes past the end of its array.

This approach is particularly effective if the arrays are already sorted (a follow-up question), as the sorting step can be skipped, making the algorithm run in linear time.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i = 0, j = 0;
        List<Integer> intersection = new ArrayList<>();
        
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                intersection.add(nums1[i]);
                i++;
                j++;
            }
        }
        
        // Convert List to array
        int[] result = new int[intersection.size()];
        for (int k = 0; k < intersection.size(); k++) {
            result[k] = intersection.get(k);
        }
        return result;
    }
}
```
### Algorithm
- Sort both input arrays, `nums1` and `nums2`.
- Initialize two pointers, `i = 0` for `nums1` and `j = 0` for `nums2`.
- Initialize an empty list `intersection`.
- While `i < nums1.length` and `j < nums2.length`:
  - If `nums1[i] < nums2[j]`, increment `i`.
  - Else if `nums1[i] > nums2[j]`, increment `j`.
  - Else (if `nums1[i] == nums2[j]`):
    - Add `nums1[i]` to the `intersection` list.
    - Increment both `i` and `j`.
- Convert the `intersection` list to an array and return it.

## Hash Map Frequency Counter
This is the most time-efficient approach for unsorted arrays. It involves using a hash map to store the frequencies of elements in one array. Then, we iterate through the second array and check if the element exists in the hash map. If it does, we add it to our result and decrement its frequency in the map.
**Time:** O(n + m), where `n` and `m` are the lengths of the arrays. It takes O(n) to build the frequency map from the smaller array and O(m) to iterate through the larger array. · **Space:** O(k) where `k` is the number of unique elements in the smaller array. If using an array as a frequency counter, the space is constant, O(1), as it depends on the range of values (1001) not the input size. The result list also requires up to O(min(n, m)) space.
**Pros:** Optimal time complexity for unsorted arrays.; Can be optimized with an array instead of a hash map due to value constraints.; Flexible for follow-up scenarios like one array being on disk.
**Cons:** Requires extra space for the frequency counter, which might be significant if the number of unique elements is large and their values are not constrained.
### Explanation
This approach uses a hash map to count the frequency of each element in one of the arrays. To optimize for space, it's best to use the smaller array to build this frequency map. After populating the map, we iterate through the second, larger array. For each element in the second array, we check if it's present in our map and has a count greater than zero. If it does, we add the element to our result list and decrement its count in the map. This ensures that we find all common elements with the correct multiplicity.

Given the problem constraints (`0 <= nums[i] <= 1000`), we can use a simple integer array of size 1001 as a direct-access frequency table instead of a `HashMap`, which can be slightly more performant.

This method is also excellent for the follow-up question where `nums2` is stored on disk, as we can build the map from `nums1` (if it fits in memory) and then process `nums2` as a stream without loading it all at once.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array to optimize space
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums1) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        List<Integer> intersection = new ArrayList<>();
        for (int num : nums2) {
            if (freqMap.containsKey(num) && freqMap.get(num) > 0) {
                intersection.add(num);
                freqMap.put(num, freqMap.get(num) - 1);
            }
        }
        
        // Convert List to array
        int[] result = new int[intersection.size()];
        for (int i = 0; i < intersection.size(); i++) {
            result[i] = intersection.get(i);
        }
        return result;
    }
}
```
### Algorithm
- To optimize space, identify the smaller array. Let's assume `nums1` is smaller.
- Create a frequency counter. A `HashMap` can be used, or an integer array of size 1001 given the constraints.
- Iterate through `nums1` and populate the frequency counter.
- Initialize an empty list `intersection`.
- Iterate through each number `num` in `nums2`.
- If the count for `num` in the frequency counter is greater than 0:
  - Add `num` to the `intersection` list.
  - Decrement the count for `num` in the frequency counter.
- Convert the `intersection` list to an array and return it.

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        HashSet < int > hs1 = new HashSet < int > (nums1.Concat(nums2).ToArray());
        Dictionary < int, int > dict = new Dictionary < int, int > ();
        List < int > result = new List < int > ();
        foreach(int x in hs1) {
            dict[x] = 0;
        }
        foreach(int x in nums1) {
            if (dict.ContainsKey(x)) {
                dict[x] += 1;
            } else {
                dict[x] = 1;
            }
        }
        foreach(int x in nums2) {
            if (dict[x] > 0) {
                result.Add(x);
                dict[x] -= 1;
            }
        }
        return result.ToArray();
    }
}
```

### Java

```java
class Solution {
public
  int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer, Integer> counter = new HashMap<>();
    for (int num : nums1) {
      counter.put(num, counter.getOrDefault(num, 0) + 1);
    }
    List<Integer> t = new ArrayList<>();
    for (int num : nums2) {
      if (counter.getOrDefault(num, 0) > 0) {
        t.add(num);
        counter.put(num, counter.get(num) - 1);
      }
    }
    int[] res = new int[t.size()];
    for (int i = 0; i < res.length; ++i) {
      res[i] = t.get(i);
    }
    return res;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersect =
  function (nums1, nums2) {
    const counter = {};
    for (const num of nums1) {
      counter[num] = (counter[num] || 0) + 1;
    }
    let res = [];
    for (const num of nums2) {
      if (counter[num] > 0) {
        res.push(num);
        counter[num] -= 1;
      }
    }
    return res;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> intersect(vector<int> &nums1, vector<int> &nums2) {
    unordered_map<int, int> counter;
    for (int num : nums1)
      ++counter[num];
    vector<int> res;
    for (int num : nums2) {
      if (counter[num] > 0) {
        --counter[num];
        res.push_back(num);
      }
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: counter = Counter(nums1) res = [] for num in nums2: if counter[num] > 0: res . append(num) counter[num] -= 1 return res  # class Solution ( object ): def intersect ( self , nums1 , nums2 ): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ ans = [] nums1 . sort () nums2 . sort () i = j = 0 while i < len ( nums1 ) and j < len ( nums2 ): if nums1 [ i ] < nums2 [ j ]: i += 1 elif nums1 [ i ] > nums2 [ j ]: j += 1 else : ans . append ( nums1 [ i ]) i += 1 j += 1 return ans

```