Problem Description

You have two arrays nums1 and nums2, both containing integers and having the same even length n. Your task is to:

1. Remove exactly n/2 elements from nums1
2. Remove exactly n/2 elements from nums2
3. Take all remaining elements from both arrays and put them into a set s (which automatically removes duplicates)
4. Find the maximum possible size of this set

The goal is to strategically choose which elements to remove from each array so that when you combine the remaining elements into a set, you get as many unique elements as possible.

For example, if you have:

• nums1 = [1, 2, 3, 4] and nums2 = [3, 4, 5, 6]
• You need to remove 2 elements from each array
• If you keep [1, 2] from nums1 and [5, 6] from nums2
• The resulting set would be {1, 2, 5, 6} with size 4

The challenge is finding the optimal removal strategy to maximize the number of unique elements in the final set.

Intuition

To maximize the number of unique elements in the final set, we need to think about what types of elements exist across both arrays:

1. Elements that appear only in nums1 (unique to nums1)
2. Elements that appear only in nums2 (unique to nums2)
3. Elements that appear in both arrays (common elements)

The key insight is that we want to keep as many different unique elements as possible. Since we must keep exactly n/2 elements from each array, our strategy should be:

• From nums1, prioritize keeping elements that are unique to nums1 (not in nums2), because these elements won't be available from nums2
• From nums2, prioritize keeping elements that are unique to nums2 (not in nums1), because these elements won't be available from nums1
• For common elements that appear in both arrays, we can get them from either array, so they serve as "flexible" choices

Let's denote:

• s1 - s2 = elements unique to nums1
• s2 - s1 = elements unique to nums2
• s1 & s2 = common elements in both arrays

The maximum number of unique-to-nums1 elements we can keep is min(len(s1 - s2), n/2) because we can only keep n/2 elements total from nums1.

Similarly, the maximum number of unique-to-nums2 elements we can keep is min(len(s2 - s1), n/2).

After keeping these unique elements, any remaining slots from our n/2 quota in each array can be filled with common elements. Since common elements appear in both arrays, we can access all of them regardless of our choices.

The final answer is the sum of:

• Unique elements we keep from nums1
• Unique elements we keep from nums2
• All common elements (since we can always access them)

However, this sum is capped at n (the total number of elements we keep from both arrays combined).

Learn more about Greedy patterns.

Solution Approach

The implementation follows the intuition by using set operations to categorize elements:

1. Convert arrays to sets: First, we create sets from both input arrays:

   s1 = set(nums1)
   s2 = set(nums2)

   This removes duplicates within each array and enables efficient set operations.

2. Calculate unique elements from each array:

   • len(s1 - s2) gives the count of elements unique to nums1
   • len(s2 - s1) gives the count of elements unique to nums2

   Since we can only keep n/2 elements from each array, we take the minimum:

   a = min(len(s1 - s2), n // 2)  # max unique elements we can keep from nums1
   b = min(len(s2 - s1), n // 2)  # max unique elements we can keep from nums2

3. Calculate common elements:

   • len(s1 & s2) gives the count of elements that appear in both arrays
   • These common elements are always accessible since we can pick them from either array when filling remaining slots

4. Compute the final result:

   return min(a + b + len(s1 & s2), n)

   The sum a + b + len(s1 & s2) represents:

   • a: unique elements kept from nums1
   • b: unique elements kept from nums2
   • len(s1 & s2): all common elements (accessible from remaining slots)

   We cap this at n because we're only keeping n total elements (n/2 from each array).

The algorithm efficiently uses set operations with O(n) time complexity for set creation and O(1) space for the intermediate variables, making it optimal for this problem.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach:

Input: nums1 = [1, 1, 2, 3, 4], nums2 = [2, 3, 5, 5, 6], n = 6 (arrays have length 6 each)

Step 1: Convert arrays to sets

• s1 = {1, 2, 3, 4} (removes duplicate 1 from nums1)
• s2 = {2, 3, 5, 6} (removes duplicate 5 from nums2)

Step 2: Identify element categories

• Elements unique to nums1: s1 - s2 = {1, 4} (2 elements)
• Elements unique to nums2: s2 - s1 = {5, 6} (2 elements)
• Common elements: s1 & s2 = {2, 3} (2 elements)

Step 3: Calculate maximum unique elements we can keep

• From nums1, we need to keep exactly n/2 = 3 elements

  • We can keep at most min(2, 3) = 2 unique elements from nums1 (elements 1 and 4)
  • This leaves 1 slot that must be filled with a common element

• From nums2, we need to keep exactly n/2 = 3 elements

  • We can keep at most min(2, 3) = 2 unique elements from nums2 (elements 5 and 6)
  • This leaves 1 slot that must be filled with a common element

Step 4: Calculate the final result

• Unique from nums1: 2 elements ({1, 4})
• Unique from nums2: 2 elements ({5, 6})
• Common elements: 2 elements ({2, 3}) - we can access both since we have remaining slots
• Total: min(2 + 2 + 2, 6) = 6

Optimal selection:

• Keep from nums1: [1, 4, 2] or [1, 4, 3] (2 unique + 1 common)
• Keep from nums2: [5, 6, 3] or [5, 6, 2] (2 unique + 1 common)
• Final set: {1, 2, 3, 4, 5, 6} with size = 6

The algorithm correctly identifies that by prioritizing unique elements from each array and using common elements to fill remaining slots, we can achieve the maximum possible set size of 6.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m) where n = len(nums1) and m = len(nums2)

• Converting nums1 to set s1: O(n)
• Converting nums2 to set s2: O(m)
• Computing s1 - s2 (set difference): O(len(s1)) which is at most O(n)
• Computing s2 - s1 (set difference): O(len(s2)) which is at most O(m)
• Computing s1 & s2 (set intersection): O(min(len(s1), len(s2))) which is at most O(min(n, m))
• The min and len operations are O(1) for the final calculations

Overall time complexity is O(n + m), which simplifies to O(n) since both arrays have the same length n.

Space Complexity: O(n + m) which simplifies to O(n)

• Creating set s1 from nums1: O(n) space
• Creating set s2 from nums2: O(m) space
• The set operations (s1 - s2, s2 - s1, s1 & s2) create new sets but their space is bounded by the original sets' sizes
• Variables a, b, and n use O(1) space

Since both input arrays have the same length n, the space complexity is O(n + n) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Greedy Strategy for Common Elements

The Mistake: A common error is thinking that we should always try to maximize the unique elements from each array first, then "fill in" with common elements if we have space left. This leads to incorrect logic like:

# INCORRECT approach
unique_from_nums1 = len(set1 - set2)
unique_from_nums2 = len(set2 - set1)
common = len(set1 & set2)

# Wrong: trying to take all unique elements first
if unique_from_nums1 <= n//2 and unique_from_nums2 <= n//2:
    result = unique_from_nums1 + unique_from_nums2 + min(common, n - unique_from_nums1 - unique_from_nums2)

Why It's Wrong: The issue is that after selecting unique elements from each array, you might not have enough "slots" left to accommodate all common elements optimally. The common elements are accessible from BOTH arrays, so they offer flexibility in selection.

The Correct Understanding: The solution correctly recognizes that:

• We can keep at most n/2 elements from each array
• Unique elements from nums1 can ONLY come from nums1
• Unique elements from nums2 can ONLY come from nums2
• Common elements can come from EITHER array

So the formula min(unique_to_set1 + unique_to_set2 + common_elements, n) works because:

• If unique_to_set1 + unique_to_set2 < n, we have "spare slots" that can be filled with common elements
• The common elements are always available since we can strategically choose which array to pick them from

Pitfall 2: Forgetting to Handle Duplicate Elements Within Each Array

The Mistake: Working directly with the original arrays without converting to sets first:

# INCORRECT - doesn't handle duplicates within arrays
n = len(nums1)
# This counts duplicates multiple times
unique_to_nums1 = sum(1 for x in nums1 if x not in nums2)  

Why It's Wrong: If nums1 = [1, 1, 2, 2] and nums2 = [3, 3, 4, 4], the above code would count 4 unique elements in nums1, but there are actually only 2 unique values (1 and 2).

The Solution: Always convert to sets first to eliminate duplicates:

set1 = set(nums1)  # Removes duplicates
set2 = set(nums2)  # Removes duplicates
unique_to_set1 = len(set1 - set2)  # Now counting unique VALUES, not occurrences

Pitfall 3: Incorrect Calculation of Available Slots

The Mistake: Assuming we can keep more than n/2 elements from one array if we keep fewer from the other:

# INCORRECT logic
if len(set1 - set2) > n//2:
    # Wrong: thinking we can keep more from nums1 if we keep less from nums2
    extra_from_nums1 = len(set1 - set2) - n//2
    available_from_nums2 = n//2 - extra_from_nums1

Why It's Wrong: The problem explicitly states we must remove EXACTLY n/2 elements from each array, meaning we keep EXACTLY n/2 from each. This is a hard constraint, not flexible.

The Correct Approach: Always cap the unique elements at n/2 for each array:

unique_to_set1 = min(len(set1 - set2), n // 2)  # Never exceed n/2
unique_to_set2 = min(len(set2 - set1), n // 2)  # Never exceed n/2