# Find the Difference of Two Arrays
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-difference-of-two-arrays)
Canonical: https://scaleengineer.com/dsa/problems/find-the-difference-of-two-arrays
**Data structures:** Array, Hash Table
**Companies:** [Yandex](https://scaleengineer.com/companies/yandex)
---
## Problem
Given two **0-indexed** integer arrays `nums1` and `nums2`, return _a list_ `answer` _of size_ `2` _where:_

* `answer[0]` _is a list of all **distinct** integers in_ `nums1` _which are **not** present in_ `nums2`_._
* `answer[1]` _is a list of all **distinct** integers in_ `nums2` _which are **not** present in_ `nums1`.

**Note** that the integers in the lists may be returned in **any** order.

**Example 1:**

**Input:** nums1 = [1,2,3], nums2 = [2,4,6]
**Output:** [[1,3],[4,6]]
**Explanation:**
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums1. Therefore, answer[1] = [4,6].

**Example 2:**

**Input:** nums1 = [1,2,3,3], nums2 = [1,1,2,2]
**Output:** [[3],[]]
**Explanation:**
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

**Constraints:**

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

# Approaches
## Brute Force with Nested Loops
This approach directly translates the problem statement into code. We iterate through each element of the first array and, for each element, we scan the entire second array to see if a match exists. We repeat the process for the second array against the first. To handle the requirement for distinct elements in the output, we use sets to store our results before converting them to lists.
**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`. The same happens for `nums2` against `nums1`. · **Space:** O(n + m) in the worst case, to store the result sets. If all elements in `nums1` are unique and not in `nums2`, and vice-versa, the sets will store `n` and `m` elements respectively.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient for large arrays, likely resulting in a 'Time Limit Exceeded' error on most coding platforms.
### Explanation
We need to find two lists: `diff1` (elements in `nums1` but not `nums2`) and `diff2` (elements in `nums2` but not `nums1`).

To find `diff1`, we iterate through each number `num1` in `nums1`. For each `num1`, we perform a linear search through `nums2`. If after checking all elements of `nums2`, we don't find `num1`, we add it to a result set to ensure uniqueness.

Similarly, to find `diff2`, we iterate through each number `num2` in `nums2` and search for it in `nums1`. If not found, it's added to another result set.

Using sets (`HashSet` in Java) for the results is crucial to automatically handle duplicates from the input arrays (e.g., `[1,2,3,3]`) and ensure the final output lists contain only distinct integers.

Finally, the two sets are converted into lists and returned.

```java
import java.util.*;

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> diff1 = new HashSet<>();
        Set<Integer> diff2 = new HashSet<>();

        // Find elements in nums1 but not in nums2
        for (int num1 : nums1) {
            boolean found = false;
            for (int num2 : nums2) {
                if (num1 == num2) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                diff1.add(num1);
            }
        }

        // Find elements in nums2 but not in nums1
        for (int num2 : nums2) {
            boolean found = false;
            for (int num1 : nums1) {
                if (num2 == num1) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                diff2.add(num2);
            }
        }

        List<List<Integer>> answer = new ArrayList<>();
        answer.add(new ArrayList<>(diff1));
        answer.add(new ArrayList<>(diff2));
        return answer;
    }
}
```
### Algorithm
- Initialize two empty sets, `resultSet1` and `resultSet2`, to store the unique differences.
- For each element `num1` in `nums1`:
  - Set a boolean flag `is_present` to `false`.
  - Iterate through each element `num2` in `nums2`.
  - If `num1` equals `num2`, set `is_present` to `true` and break the inner loop.
  - If the inner loop completes and `is_present` is `false`, add `num1` to `resultSet1`.
- Repeat the process, swapping the roles of `nums1` and `nums2` to populate `resultSet2`.
- Convert `resultSet1` and `resultSet2` to lists.
- Return a list containing the two result lists.

## Sorting and Two Pointers
A more optimized approach involves sorting both arrays first. Once sorted, we can use a two-pointer technique to compare elements from both arrays in a single pass. This avoids the nested loops of the brute-force method.
**Time:** O(n log n + m log m), where `n` and `m` are the lengths of the arrays. The sorting steps take O(n log n) and O(m log m), and the subsequent two-pointer scan takes O(n + m). The sorting is the bottleneck. · **Space:** O(n + m) for the output lists. The space used by the sorting algorithm (e.g., `Arrays.sort` in Java uses O(log n) for primitives) is typically less than the space for the output.
**Pros:** Much more efficient than brute force for large arrays.
**Cons:** The sorting step dominates the time complexity.; Can be slightly more complex to implement correctly, especially handling duplicates.
### Explanation
The core idea is that if both arrays are sorted, we can find the differences efficiently. We initialize two pointers, `i` for `nums1` and `j` for `nums2`, both starting at index 0.

We then compare `nums1[i]` and `nums2[j]`:
- If `nums1[i] < nums2[j]`, it means `nums1[i]` is not present in `nums2`. We add `nums1[i]` to our difference list for `nums1` and advance pointer `i`.
- If `nums1[i] > nums2[j]`, it means `nums2[j]` is not present in `nums1`. We add `nums2[j]` to the difference list for `nums2` and advance pointer `j`.
- If `nums1[i] == nums2[j]`, the element is common, so we advance both pointers.

A crucial part is handling duplicates. After processing an element, we must advance the pointer past all subsequent occurrences of that same element. We use sets to collect the results to naturally handle the distinctness requirement.

After the main loop finishes, one of the arrays might still have remaining elements. These are all guaranteed to be unique to that array, so we add them to the appropriate difference list.

```java
import java.util.*;

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        Set<Integer> diff1 = new HashSet<>();
        Set<Integer> diff2 = new HashSet<>();

        int i = 0, j = 0;
        int n = nums1.length;
        int m = nums2.length;

        while (i < n && j < m) {
            if (nums1[i] < nums2[j]) {
                diff1.add(nums1[i]);
                i++;
            } else if (nums1[i] > nums2[j]) {
                diff2.add(nums2[j]);
                j++;
            } else { // nums1[i] == nums2[j]
                int commonVal = nums1[i];
                while (i < n && nums1[i] == commonVal) {
                    i++;
                }
                while (j < m && nums2[j] == commonVal) {
                    j++;
                }
            }
        }

        // Add remaining elements from nums1
        while (i < n) {
            diff1.add(nums1[i]);
            i++;
        }

        // Add remaining elements from nums2
        while (j < m) {
            diff2.add(nums2[j]);
            j++;
        }

        List<List<Integer>> answer = new ArrayList<>();
        answer.add(new ArrayList<>(diff1));
        answer.add(new ArrayList<>(diff2));
        return answer;
    }
}
```
### Algorithm
- Sort the input arrays `nums1` and `nums2`.
- Initialize two pointers, `i = 0` and `j = 0`, for `nums1` and `nums2` respectively.
- Initialize two sets, `diff1` and `diff2`, to store the results.
- While `i` is within the bounds of `nums1` and `j` is within the bounds of `nums2`:
  - If `nums1[i] < nums2[j]`, add `nums1[i]` to `diff1` and increment `i`.
  - If `nums1[i] > nums2[j]`, add `nums2[j]` to `diff2` and increment `j`.
  - If `nums1[i] == nums2[j]`, it's a common element. Store the value, then advance `i` past all duplicates of this value in `nums1` and advance `j` past all duplicates in `nums2`.
- After the loop, if there are remaining elements in `nums1` (i.e., `i < nums1.length`), add them all to `diff1`.
- Similarly, if there are remaining elements in `nums2`, add them all to `diff2`.
- Convert the sets to lists and return.

## Using Hash Sets for Optimal Performance
The most efficient approach utilizes hash sets to achieve linear time complexity. By converting both input arrays into sets, we can leverage the O(1) average time complexity of set lookups (the `contains` operation) to find the differences quickly.
**Time:** O(n + m) on average. It takes O(n) to build `set1`, O(m) to build `set2`, O(n) to iterate `set1` and check `set2`, and O(m) to iterate `set2` and check `set1`. · **Space:** O(n + m). We need space for `set1` (up to `n` elements) and `set2` (up to `m` elements), in addition to the space for the final answer lists.
**Pros:** Optimal time complexity.; The code is often simpler and more declarative than the two-pointer approach.
**Cons:** Uses extra space to store the two sets, which might be a concern in memory-constrained environments.
### Explanation
First, we convert `nums1` and `nums2` into two separate hash sets, `set1` and `set2`. This step has two benefits: it gives us fast O(1) lookups, and it automatically handles any duplicate numbers within the original arrays.

Next, we find the elements that are unique to `nums1`. We iterate through every number in `set1` and check if it exists in `set2`. If a number from `set1` is *not* found in `set2`, we add it to our first result list.

Then, we do the reverse. We iterate through every number in `set2` and check if it exists in `set1`. If a number from `set2` is *not* found in `set1`, we add it to our second result list.

Finally, we return the two result lists. This method is clean, easy to read, and highly performant.

```java
import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        // Step 1: Convert arrays to sets to get unique elements
        Set<Integer> set1 = new HashSet<>();
        for (int num : nums1) {
            set1.add(num);
        }

        Set<Integer> set2 = new HashSet<>();
        for (int num : nums2) {
            set2.add(num);
        }

        // Step 2: Find elements in set1 but not in set2
        List<Integer> diff1 = new ArrayList<>();
        for (int num : set1) {
            if (!set2.contains(num)) {
                diff1.add(num);
            }
        }

        // Step 3: Find elements in set2 but not in set1
        List<Integer> diff2 = new ArrayList<>();
        for (int num : set2) {
            if (!set1.contains(num)) {
                diff2.add(num);
            }
        }

        // Step 4: Return the result
        List<List<Integer>> answer = new ArrayList<>();
        answer.add(diff1);
        answer.add(diff2);
        return answer;
    }
}
```
### Algorithm
- Create a hash set, `set1`, and populate it with all elements from `nums1`.
- Create another hash set, `set2`, and populate it with all elements from `nums2`.
- Initialize an empty list, `diff1`.
- Iterate through each `num` in `set1`. If `set2.contains(num)` is false, add `num` to `diff1`.
- Initialize an empty list, `diff2`.
- Iterate through each `num` in `set2`. If `set1.contains(num)` is false, add `num` to `diff2`.
- Return a list containing `diff1` and `diff2`.

# Solutions
### Java

```java
class Solution {
public
  List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
    Set<Integer> s1 = convert(nums1);
    Set<Integer> s2 = convert(nums2);
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> l1 = new ArrayList<>();
    List<Integer> l2 = new ArrayList<>();
    for (int v : s1) {
      if (!s2.contains(v)) {
        l1.add(v);
      }
    }
    for (int v : s2) {
      if (!s1.contains(v)) {
        l2.add(v);
      }
    }
    ans.add(l1);
    ans.add(l2);
    return ans;
  }
private
  Set<Integer> convert(int[] nums) {
    Set<Integer> s = new HashSet<>();
    for (int v : nums) {
      s.add(v);
    }
    return s;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[][]} */ var findDifference =
  function (nums1, nums2) {
    let ans1 = new Set(nums1),
      ans2 = new Set(nums2);
    for (let num of nums1) {
      ans2.delete(num);
    }
    for (let num of nums2) {
      ans1.delete(num);
    }
    return [Array.from(ans1), Array.from(ans2)];
  };

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> findDifference(vector<int> &nums1, vector<int> &nums2) {
    unordered_set<int> s1(nums1.begin(), nums1.end());
    unordered_set<int> s2(nums2.begin(), nums2.end());
    vector<vector<int>> ans(2);
    for (int v : s1)
      if (!s2.count(v))
        ans[0].push_back(v);
    for (int v : s2)
      if (!s1.count(v))
        ans[1].push_back(v);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]: s1, s2 = set(nums1), set(nums2) return [list(s1 - s2), list(s2 - s1)]

```