# Maximum Size of a Set After Removals
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-size-of-a-set-after-removals)
Canonical: https://scaleengineer.com/dsa/problems/maximum-size-of-a-set-after-removals
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table
---
## Problem
You are given two **0-indexed** integer arrays `nums1` and `nums2` of even length `n`.

You must remove `n / 2` elements from `nums1` and `n / 2` elements from `nums2`. After the removals, you insert the remaining elements of `nums1` and `nums2` into a set `s`.

Return _the **maximum** possible size of the set_ `s`.

**Example 1:**

**Input:** nums1 = [1,2,1,2], nums2 = [1,1,1,1]
**Output:** 2
**Explanation:** We remove two occurences of 1 from nums1 and nums2. After the removals, the arrays become equal to nums1 = [2,2] and nums2 = [1,1]. Therefore, s = {1,2}.
It can be shown that 2 is the maximum possible size of the set s after the removals.

**Example 2:**

**Input:** nums1 = [1,2,3,4,5,6], nums2 = [2,3,2,3,2,3]
**Output:** 5
**Explanation:** We remove 2, 3, and 6 from nums1, as well as 2 and two occurrences of 3 from nums2. After the removals, the arrays become equal to nums1 = [1,4,5] and nums2 = [2,3,2]. Therefore, s = {1,2,3,4,5}.
It can be shown that 5 is the maximum possible size of the set s after the removals.

**Example 3:**

**Input:** nums1 = [1,1,2,2,3,3], nums2 = [4,4,5,5,6,6]
**Output:** 6
**Explanation:** We remove 1, 2, and 3 from nums1, as well as 4, 5, and 6 from nums2. After the removals, the arrays become equal to nums1 = [1,2,3] and nums2 = [4,5,6]. Therefore, s = {1,2,3,4,5,6}.
It can be shown that 6 is the maximum possible size of the set s after the removals.

**Constraints:**

* `n == nums1.length == nums2.length`
* `1 <= n <= 2 * 104`
* `n` is even.
* `1 <= nums1[i], nums2[i] <= 109`

# Approaches
## Greedy Approach with Hash Sets
This approach uses hash sets to efficiently identify the unique elements in each array. A greedy strategy is then applied to determine the maximum possible size of the final set. The core idea is to calculate the maximum number of unique elements that can be contributed by each array and combine them, while respecting the total number of unique elements available across both arrays.
**Time:** O(n), where n is the length of the arrays. This is because populating the two hash sets takes O(n) time, and finding their union also takes O(n) time in the worst case. The remaining calculations are done in constant time. · **Space:** O(n) in the worst case. The space is used to store up to `n` unique elements from `nums1` and `n` unique elements from `nums2` in the hash sets. The union set can also store up to `n` unique elements in this problem's context.
**Pros:** **Optimal Time Complexity**: The solution runs in O(n) time, which is optimal as we must inspect every element at least once.; **Simplicity**: The logic is straightforward and relies on a simple, elegant formula, making the code easy to write and understand.; **Efficient Memory Usage**: While it uses extra space, `HashSet` provides fast lookups and insertions, making the overall process very efficient.
**Cons:** **Space Usage**: The approach requires O(n) extra space in the worst case to store the unique elements in hash sets. For very large `n` where memory is constrained, this could be a drawback.
### Explanation
To solve this problem, we want to maximize the number of unique elements in the final set. The final set is formed by the union of the remaining elements from `nums1` and `nums2` after removing `n/2` elements from each.

The key insight is to think about the constraints on the number of unique elements we can select. From `nums1`, we keep `n/2` elements. The number of unique elements among these is limited by both the number of unique elements available in `nums1` and the count `n/2`. Similarly for `nums2`.

Let's formalize this:
1.  Let `s1` be the set of unique elements in `nums1` and `s2` be the set of unique elements in `nums2`.
2.  From `nums1`, we can keep at most `n/2` elements. Therefore, the maximum number of *unique* elements we can choose to keep from `nums1` is `u1 = min(|s1|, n/2)`.
3.  Similarly, the maximum number of *unique* elements we can keep from `nums2` is `u2 = min(|s2|, n/2)`.
4.  If we could choose these `u1` and `u2` elements to be completely distinct, the total size of the final set would be `u1 + u2`.
5.  However, the elements we choose must come from the original pool of unique elements, `s1 U s2`. The total number of unique elements available across both arrays is `|s1 U s2|`.
6.  Therefore, the size of our final set is capped by this total availability. The maximum size is the smaller of the number of elements we can pick and the number of elements that are available to be picked.

This leads to the final formula: `result = min(|s1 U s2|, u1 + u2)`.

Here is the implementation in Java:
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maximumSetSize(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int n_half = n / 2;

        // Step 1: Find unique elements in each array using HashSets.
        Set<Integer> s1 = new HashSet<>();
        for (int num : nums1) {
            s1.add(num);
        }

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

        // Step 2: Calculate the max unique elements we can keep from each array.
        int u1 = Math.min(s1.size(), n_half);
        int u2 = Math.min(s2.size(), n_half);

        // Step 3: Calculate the total number of unique elements available across both arrays.
        Set<Integer> union = new HashSet<>(s1);
        union.addAll(s2);
        int totalUnique = union.size();

        // Step 4: The result is the minimum of the total available unique elements
        // and the sum of unique elements we can pick from each array.
        return Math.min(totalUnique, u1 + u2);
    }
}
```
### Algorithm
- Get the length of the arrays, `n`, and calculate `n_half = n / 2`.
- Create a `HashSet` `s1` from `nums1` to find its unique elements.
- Create a `HashSet` `s2` from `nums2` to find its unique elements.
- Calculate the maximum number of unique elements that can be kept from `nums1`: `u1 = min(s1.size(), n_half)`.
- Calculate the maximum number of unique elements that can be kept from `nums2`: `u2 = min(s2.size(), n_half)`.
- Find the total number of unique elements across both arrays by taking the size of the union of `s1` and `s2`: `totalUnique = |s1 U s2|`.
- The maximum size of the final set is `min(totalUnique, u1 + u2)`.

# Solutions
### Java

```java
class Solution {
public
  int maximumSetSize(int[] nums1, int[] nums2) {
    Set<Integer> s1 = new HashSet<>();
    Set<Integer> s2 = new HashSet<>();
    for (int x : nums1) {
      s1.add(x);
    }
    for (int x : nums2) {
      s2.add(x);
    }
    int n = nums1.length;
    int a = 0, b = 0, c = 0;
    for (int x : s1) {
      if (!s2.contains(x)) {
        ++a;
      }
    }
    for (int x : s2) {
      if (!s1.contains(x)) {
        ++b;
      } else {
        ++c;
      }
    }
    a = Math.min(a, n / 2);
    b = Math.min(b, n / 2);
    return Math.min(a + b + c, n);
  }
}

```

### Python

```python
class Solution:
    def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int: s1 = set(nums1) s2 = set(nums2) n = len(nums1) a = min(len(s1 - s2), n // 2) b = min(len(s2 - s1), n // 2) return min(a + b + len(s1 & s2), n)

```

### CPP

```cpp
class Solution {
public:
  int maximumSetSize(vector<int> &nums1, vector<int> &nums2) {
    unordered_set<int> s1(nums1.begin(), nums1.end());
    unordered_set<int> s2(nums2.begin(), nums2.end());
    int n = nums1.size();
    int a = 0, b = 0, c = 0;
    for (int x : s1) {
      if (!s2.count(x)) {
        ++a;
      }
    }
    for (int x : s2) {
      if (!s1.count(x)) {
        ++b;
      } else {
        ++c;
      }
    }
    a = min(a, n / 2);
    b = min(b, n / 2);
    return min(a + b + c, n);
  }
};

```