# Intersection of Two Arrays
**Difficulty:** EASY
[External](https://leetcode.com/problems/intersection-of-two-arrays)
Canonical: https://scaleengineer.com/dsa/problems/intersection-of-two-arrays
**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:** [Criteo](https://scaleengineer.com/companies/criteo), [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Nvidia](https://scaleengineer.com/companies/nvidia), [PayPal](https://scaleengineer.com/companies/paypal), [Wix](https://scaleengineer.com/companies/wix), [Yandex](https://scaleengineer.com/companies/yandex), [tcs](https://scaleengineer.com/companies/tcs), [MongoDB](https://scaleengineer.com/companies/mongodb), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [CVENT](https://scaleengineer.com/companies/cvent)
---
## Problem
Given two integer arrays `nums1` and `nums2`, return _an array of their intersection_. Each element in the result must be **unique** and you may return the result in **any order**.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

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

# Approaches
## Brute Force with Nested Loops
This straightforward approach involves using nested loops. We iterate through every element of the first array and, for each element, we iterate through the entire second array to check for a match. To ensure the final result contains only unique elements, we use a `HashSet` to store the common numbers we find.
**Time:** O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. For each of the `n` elements in `nums1`, we iterate through all `m` elements of `nums2`. · **Space:** O(k), where k is the number of unique elements in the intersection. This space is used by the `HashSet` to store the result. In the worst case, k can be `min(nums1.length, nums2.length)`.
**Pros:** Simple to understand and implement.; Requires minimal auxiliary data structures (only for the result).
**Cons:** Extremely inefficient for larger arrays, with a quadratic time complexity.; Likely to result in a 'Time Limit Exceeded' (TLE) error on most online judges for non-trivial input sizes.
### Explanation
The brute-force method is the most intuitive way to solve the problem. We take each element from the first array, `nums1`, and compare it against every element in the second array, `nums2`. If a match is found, we add it to a separate data structure that stores our results.

To meet the requirement that each element in the result must be unique, a `HashSet` is an ideal choice for storing the intersection. A `HashSet` does not allow duplicate values, so if we find a common number multiple times, it will only be stored once.

After checking all pairs of elements, the `HashSet` will contain the complete, unique intersection of the two arrays. The final step is to convert this `HashSet` into an array before returning it.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> resultSet = new HashSet<>();
        
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                if (num1 == num2) {
                    resultSet.add(num1);
                    break; // Optimization: once found, move to the next num1
                }
            }
        }
        
        // Convert the HashSet to an array
        int[] result = new int[resultSet.size()];
        int i = 0;
        for (int num : resultSet) {
            result[i++] = num;
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize an empty `HashSet` called `resultSet` to store the unique intersection elements.
- Iterate through each element `num1` in the first array, `nums1`.
- For each `num1`, start a nested loop to iterate through each element `num2` in the second array, `nums2`.
- Inside the nested loop, compare `num1` and `num2`.
- If `num1` is equal to `num2`, it means we've found a common element. Add this element to the `resultSet`. The `HashSet` will automatically handle duplicates.
- After both loops have finished, the `resultSet` contains all unique common elements.
- Create a new integer array with a size equal to the size of the `resultSet`.
- Iterate through the `resultSet` and copy each element into the new array.
- Return the final array.

## Sorting and Two Pointers
This approach improves upon the brute-force method by first sorting both arrays. Once sorted, we can use a two-pointer technique to find the intersection in a single pass. Two pointers, one for each array, traverse the arrays, and because they are sorted, we can efficiently find common elements.
**Time:** O(n log n + m log m), where `n` and `m` are the lengths of the arrays. The sorting of both arrays is the most time-consuming part of this algorithm. The subsequent two-pointer scan takes O(n + m) time. · **Space:** O(k), where k is the number of elements in the intersection. This space is for the `HashSet` that stores the result. Note that the sorting algorithm might use additional space, typically O(log n + log m) for quicksort or O(n + m) for mergesort, depending on the Java standard library's implementation.
**Pros:** Significantly more efficient than the brute-force approach.; Very efficient if the arrays are already sorted.; The two-pointer scan itself has a linear time complexity O(n + m).
**Cons:** The time complexity is dominated by the sorting step, making it less efficient than the hash set approach for unsorted arrays.; If in-place sorting is used, it modifies the original arrays. If not, it requires extra space to hold the sorted copies.
### Explanation
By sorting the arrays, we can compare their elements in a more structured way. We initialize two pointers, one at the beginning of each sorted array. We then compare the elements pointed to by these pointers.

- If the element in the first array is smaller than the element in the second, we know it can't be in the intersection (since the second array is sorted), so we move the first pointer forward.
- Similarly, if the element in the second array is smaller, we move the second pointer forward.
- If the elements are equal, we've found a number that's in both arrays. We add it to our result set (a `HashSet` to handle duplicates) and advance both pointers to continue our search.

We repeat this process until one of the pointers goes past the end of its array. Finally, we convert the result set into an array.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        Set<Integer> resultSet = new HashSet<>();
        int i = 0, j = 0;
        
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else { // nums1[i] == nums2[j]
                resultSet.add(nums1[i]);
                i++;
                j++;
            }
        }
        
        int[] result = new int[resultSet.size()];
        int k = 0;
        for (int num : resultSet) {
            result[k++] = num;
        }
        
        return result;
    }
}
```
### Algorithm
- Sort both input arrays, `nums1` and `nums2`.
- Initialize an empty `HashSet`, `resultSet`, to store the unique intersection elements.
- Initialize two pointers: `i` starting at the beginning of `nums1` and `j` starting at the beginning of `nums2`.
- Loop while both pointers are within the bounds of their respective arrays (`i < nums1.length` and `j < nums2.length`).
- Compare the elements at the current pointers: `nums1[i]` and `nums2[j]`.
  - If `nums1[i]` is less than `nums2[j]`, it means `nums1[i]` is smaller and cannot be a match for `nums2[j]`, so we advance the pointer `i`.
  - If `nums1[i]` is greater than `nums2[j]`, it means `nums2[j]` is smaller, so we advance the pointer `j`.
  - If `nums1[i]` is equal to `nums2[j]`, we have found a common element. Add it to `resultSet` and advance both pointers `i` and `j` to look for the next potential match.
- After the loop terminates, convert the `resultSet` to an array and return it.

## Using Hash Sets
This is the most time-efficient approach on average. It leverages the constant-time O(1) performance of hash set lookups. First, we convert one of the arrays into a `HashSet` to get its unique elements. Then, we iterate through the second array and, for each of its elements, we check if it exists in the hash set. If it does, we add it to a result set.
**Time:** O(n + m) on average, where `n` and `m` are the lengths of the arrays. It takes O(n) to build the set from `nums1` and O(m) to iterate through `nums2` and perform lookups, which are O(1) on average. · **Space:** O(min(n, m) + k), where `n` and `m` are the array lengths, and `k` is the number of intersection elements. We use space for a hash set built from the smaller array (O(min(n, m))) and for the result set (O(k)).
**Pros:** Optimal average time complexity of O(n + m).; Simple and clean implementation.; Handles duplicates in the input arrays and the output requirement naturally due to the properties of `HashSet`.
**Cons:** Requires extra space for the hash sets. The space complexity is proportional to the size of the smaller array plus the size of the intersection.
### Explanation
The core idea is to trade space for time. By storing all unique elements of one array in a `HashSet`, we can check for the presence of an element in O(1) average time.

The algorithm proceeds as follows:
1.  Create a `HashSet` from the elements of `nums1`. This automatically handles any duplicates within `nums1` and prepares for fast lookups.
2.  Initialize a second `HashSet` to store the intersection results, ensuring the output is also unique.
3.  Iterate through `nums2`. For each number in `nums2`, check if it's in the set created from `nums1`. 
4.  If it is, add it to the intersection set.
5.  Finally, convert the intersection set to an array.

For a small optimization, we can build the initial set from the smaller of the two arrays to minimize the space used.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array to optimize space
        if (nums1.length > nums2.length) {
            return intersection(nums2, nums1);
        }

        Set<Integer> set1 = new HashSet<>();
        for (int num : nums1) {
            set1.add(num);
        }
        
        Set<Integer> resultSet = new HashSet<>();
        for (int num : nums2) {
            if (set1.contains(num)) {
                resultSet.add(num);
            }
        }
        
        int[] result = new int[resultSet.size()];
        int i = 0;
        for (int num : resultSet) {
            result[i++] = num;
        }
        
        return result;
    }
}
```
### Algorithm
- To optimize for space, identify which of the two arrays is smaller.
- Create a `HashSet` called `set` and populate it with the unique elements from the smaller array. This takes O(min(n, m)) time.
- Create another `HashSet` called `resultSet` to store the final intersection.
- Iterate through each element `num` in the larger array.
- For each `num`, check if it is present in the `set` using the `contains()` method. This is an O(1) average time operation.
- If `set.contains(num)` is true, add `num` to the `resultSet`.
- After iterating through the larger array, convert the `resultSet` into an array.
- Return the resulting array.

# Solutions
### JavaScript

```javascript
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersection =
  function (nums1, nums2) {
    const s = Array(1001).fill(false);
    for (const x of nums1) {
      s[x] = true;
    }
    const ans = [];
    for (const x of nums2) {
      if (s[x]) {
        ans.push(x);
        s[x] = false;
      }
    }
    return ans;
  };

```

### CSharp

```csharp
public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        List < int > result = new List < int > ();
        HashSet < int > arr1 = new(nums1);
        HashSet < int > arr2 = new(nums2);
        foreach(int x in arr1) {
            if (arr2.Contains(x)) {
                result.Add(x);
            }
        }
        return result.ToArray();
    }
}
```

### Java

```java
class Solution {
public
  int[] intersection(int[] nums1, int[] nums2) {
    boolean[] s = new boolean[1001];
    for (int x : nums1) {
      s[x] = true;
    }
    List<Integer> ans = new ArrayList<>();
    for (int x : nums2) {
      if (s[x]) {
        ans.add(x);
        s[x] = false;
      }
    }
    return ans.stream().mapToInt(Integer : : intValue).toArray();
  }
}

```

### Python

```python
class Solution : def intersection ( self , nums1 : List [ int ], nums2 : List [ int ]) -> List [ int ]: return list ( set ( nums1 ) & set ( nums2 )) ############ # counting class Solution : def intersection ( self , nums1 : List [ int ], nums2 : List [ int ]) -> List [ int ]: cnt = Counter ( nums1 + nums2 ) return [ x for x in arr1 if cnt [ x ] == 2 ] ############ ''' https://docs.python.org/3/reference/expressions.html#operator-precedence high to low: ** *, @, /, //, % +, - <<, >> & ^ | in, not in, is, is not, <, <=, >, >=, !=, == and or if – else ''' class Solution : def intersection ( self , nums1 : List [ int ], nums2 : List [ int ]) -> List [ int ]: s = set ( nums1 ) res = set () for num in nums2 : if num in s : res . add ( num ) return list ( res ) ############ # no extra space class Solution : def intersection ( self , nums1 : List [ int ], nums2 : List [ int ]) -> 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]) # for Leetcode 350, input with duplicates if ( not ans ) or ( len ( ans ) > 0 and ans [ - 1 ] != nums1 [ i ]): ans . append ( nums1 [ i ]) i += 1 j += 1 return ans ############ class Solution ( object ): def intersection ( self , nums1 , nums2 ): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ d = {} ans = [] for num in nums1 : d [ num ] = d . get ( num , 0 ) + 1 for num in nums2 : if num in d : ans . append ( num ) del d [ num ] return ans
```

### CPP

```cpp
class Solution {
public:
  vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
    bool s[1001];
    memset(s, false, sizeof(s));
    for (int x : nums1) {
      s[x] = true;
    }
    vector<int> ans;
    for (int x : nums2) {
      if (s[x]) {
        ans.push_back(x);
        s[x] = false;
      }
    }
    return ans;
  }
};

```