We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Size of a Set After Removals

Number: 3228

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

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. The goal is to maximize the size (i.e. the number of distinct elements) of s. Return the maximum possible size of the set s.

Key Insights

  • Each array has exactly n/2 elements remaining after removals.
  • From each array, you can keep at most n/2 distinct numbers (even if the original array has more unique numbers).
  • Many numbers may appear exclusively in one array (exclusive) or in both arrays (common). If a number appears in both arrays, you have flexibility where to “place” it in the kept subsets.
  • The high-level idea is to choose, from each array, as many unique (distinct) elements as possible. However, if one array contains too many distinct numbers, you are limited by the n/2 size. Then, you can “fill” the other array’s kept subset with some common numbers from the other array if space allows.
  • A greedy / assignment view is useful: assign each number that appears only in one array (exclusive) to that array’s kept subset – subject to a capacity of n/2 per array. Then, assign as many common numbers (appearing in both arrays) as possible into the “remaining capacities” of the two kept subsets. Finally, the answer is the total count of unique numbers you managed to “assign” (with the overall cap coming from the total unique numbers available and the overall 2*(n/2)=n kept elements).

Space and Time Complexity

Time Complexity: O(n) – we traverse the arrays a few times and work with sets/dictionaries. Space Complexity: O(n) – to store the unique elements from each array.

Solution

We first determine the capacity per array which is X = n/2. Then, we compute: • set1 = unique elements from nums1
• set2 = unique elements from nums2
Let Aonly be the count of numbers in set1 but not in set2, Bonly be the count in set2 but not in set1, and common be the count of numbers present in both sets.

Since each kept array can only hold X elements, we can use: • effective_A = min(Aonly, X) (the exclusive numbers kept from nums1)
• effective_B = min(Bonly, X) (the exclusive numbers kept from nums2)

The remaining capacity in nums1 is capacity1 = X - effective_A and in nums2 is capacity2 = X - effective_B. We can “fill” these remaining slots (total capacity = capacity1 + capacity2) with common numbers – up to however many are available. Thus, the potential maximum distinct numbers in the union is:   union_candidate = effective_A + effective_B + min(common, capacity1 + capacity2).

Since we cannot exceed the total number of unique elements overall, and also the total number of kept elements (which is n), the answer is:   answer = min(union_candidate, (Aonly + Bonly + common), n).

This assignment–interpretation ensuring that each exclusive number is “forced” to one array and common numbers are used optimally is the key insight for this problem.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def maximumSetSize(self, nums1, nums2):
        # n is the length of the arrays; each kept array will have n//2 elements.
        n = len(nums1)
        X = n // 2

        # Create sets for each array to capture unique elements.
        set1 = set(nums1)
        set2 = set(nums2)
        
        # Calculate counts for exclusive and common elements.
        Aonly = len(set1 - set2)   # Numbers only in nums1.
        Bonly = len(set2 - set1)   # Numbers only in nums2.
        common = len(set1 & set2)  # Numbers common to both arrays.
        
        # Calculate how many exclusive numbers we can assign per array.
        effective_A = min(Aonly, X)  # In nums1, we can use at most X exclusive numbers.
        effective_B = min(Bonly, X)  # In nums2, similarly.
        
        # Remaining capacity in each array's kept subset.
        capacity1 = X - effective_A
        capacity2 = X - effective_B
        total_common_capacity = capacity1 + capacity2
        
        # Maximum distinct numbers by assigning common numbers to fill remaining capacity.
        union_candidate = effective_A + effective_B + min(common, total_common_capacity)
        
        # The overall unique numbers available.
        unique_total = Aonly + Bonly + common
        
        # We cannot pick more than all unique available or more than total kept elements.
        answer = min(union_candidate, unique_total, n)
        return answer

# Example usage:
# sol = Solution()
# print(sol.maximumSetSize([1,2,1,2], [1,1,1,1]))
← Back to All Questions