# Arrays Intersection

{% hint style="info" %}
Array, Hash Table
{% endhint %}

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 num1'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?

### Solutions

#### Approach - Brute Force Technique

It works by checking each element of the first array against the second array and adding it to the intersection if it exists. The second array is represented as a list so that elements can be easily removed. This ensures that each element is counted the correct number of times.

**Steps**

1. **Initialize intersection and list2**: A new List `intersection` is created to store the intersection of `nums1` and `nums2`. Another List `list2` is created as a copy of `nums2`. This is done because elements will be removed from `list2` during the process, and we don’t want to modify the original array.
2. **Iterate over nums1**: The method iterates over each element `num` in `nums1`.
3. **Check if num exists in list2**: For each `num` in `nums1`, the method checks if `num` exists in `list2` using the `Contains` method.
4. **Add num to intersection and remove from list2**: If `num` exists in `list2`, it is added to `intersection` and removed from `list2`. The `Remove` method removes the first occurrence of `num` from `list2`. This ensures that each element in the intersection appears as many times as it shows in both arrays.
5. **Return intersection as an array**: After all elements in `nums1` have been processed, the `ToArray` method is called on `intersection` to convert it back to an array before returning it as the result of the method.

<pre class="language-csharp"><code class="lang-csharp">public class Solution
{
<strong>    public int[] Intersect(int[] nums1, int[] nums2)
</strong>    {
        List&#x3C;int> intersection = new List&#x3C;int>();
        List&#x3C;int> list2 = new List&#x3C;int>(nums2);

        foreach (int num in nums1)
        {
            if (list2.Contains(num))
            {
                intersection.Add(num);
                list2.Remove(num);
            }
        }

        return intersection.ToArray();
    }
}
</code></pre>

#### Approach - Hash Table Technique

**Steps**

1. **Initialization**: The function `Intersect` is defined with two parameters, `nums1` and `nums2`, which are the input arrays. It initializes a dictionary `dict` to keep track of the frequency of each number in `nums1`, and a list `res` to store the result.
2. **Create Frequency Dictionary**: The function iterates over each number in `nums1`. For each number, it checks if the number is already a key in `dict`. If it is, it increments the value associated with that key. If not, it adds the number as a key to `dict` with a value of 1. This results in `dict` containing each unique number in `nums1` as a key, and the frequency of that number as the value.
3. **Find Intersection**: The function then iterates over each number in `nums2`. For each number, it checks if the number is a key in `dict` and if the associated value is greater than 0. If both conditions are met, it means the number is present in both `nums1` and `nums2`, so it adds the number to `res` and decrements the value associated with the number in `dict`.
4. **Return Result**: Finally, the function converts `res` to an array and returns it. This array contains the intersection of `nums1` and `nums2`.

```csharp
public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        
        var dict = new Dictionary<int, int>();
        var res = new List<int>();

        foreach (var num in nums1)
        {
            if (dict.ContainsKey(num))
                dict[num]++;
            else
                dict[num] = 1;
        }

         foreach (var num in nums2)
        {
            if (dict.ContainsKey(num) && dict[num]>0)
            {
                res.Add(num);
                dict[num]--;
            }
        }

        return res.ToArray();
    }
}
```

> Complexity

* **Time complexity:** `O(N+M)`
* **Space complexity:** `O(N)`