Problem Statement in English

You are given two 0-indexed integer arrays nums1 and nums2, each of length n. You must remove exactly n / 2 elements from each array to make the size of the set of unique integers in the remaining elements of nums1 and nums2 as large as possible.

Return the maximum possible size of the set of unique integers in the remaining elements of nums1 and nums2.

Approach

Our answer will be the minimum of n and the sum of the unique elements from nums1 and nums2 (up to n/2 from each) plus the common elements.

We calculate the unique elements in each array and the common elements, then determine how many unique elements we can contribute from each array while respecting the n/2 removal constraint.

Remember that we can only contribute up to n/2 unique elements from each array, and the common elements can fill in the remaining budget from both sides.

And we’re done!

Solution in Python


class Solution:
    def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        half = n // 2
        set1, set2 = set(nums1), set(nums2)
        common = set1.intersection(set2)
        
        # Elements exclusive to each set
        only1 = len(set1) - len(common)
        only2 = len(set2) - len(common)
        
        # How many elements can we contribute from each array's unique pool?
        # We are capped at n // 2 for each array.
        count1 = min(only1, half)
        count2 = min(only2, half)
        
        # The total size is the sum of:
        # 1. Unique elements from nums1 (up to n/2)
        # 2. Unique elements from nums2 (up to n/2)
        # 3. Common elements (filling the remaining budget from both sides)
        return min(n, count1 + count2 + len(common))

Complexity

  • Time: $O(n)$
    Since we are iterating through both arrays to create sets and calculate intersections.

  • Space: $O(n)$
    Since we are storing the unique elements of both arrays in sets.

Mistakes I Made

I had to look this up :(

And we are done.