Maximum Size of a Set After Removals - Video Solutions

Problem Overview: You are given two arrays of equal length n. You must remove exactly n/2 elements from each array. After the removals, combine the remaining elements and compute the size of the set of distinct values. The goal is to maximize this set size.

Approach 1: Greedy with Hash Sets (O(n) time, O(n) space)

The key observation: the final answer depends only on how many distinct values you can keep. Start by converting both arrays into sets. Split the values into three groups: values unique to nums1, values unique to nums2, and values common to both. Using a greedy strategy, first keep as many elements as possible that appear only in one array because they always increase the final distinct count.

You can keep at most n/2 elements from each array. So take min(|unique1|, n/2) from the first array and min(|unique2|, n/2) from the second. After filling those slots, some capacity may remain in each array. Use that remaining capacity to include values from the common set. Since a value from the intersection contributes only once to the final set, you add at most min(|common|, remainingSlots). Hash lookups make membership checks O(1), which keeps the entire process linear.

This approach relies heavily on hash table behavior for fast uniqueness checks and on a simple greedy decision: prioritize elements that guarantee a new distinct value.

Approach 2: Sorting + Greedy Selection (O(n log n) time, O(1) extra space)

If hash sets are not preferred, you can sort both arrays using QuickSort and process them iteratively. Sorting groups duplicates together, which makes it easy to identify unique and shared values while scanning. After sorting, run two passes to determine which values belong exclusively to each array and which appear in both.

Once categorized, apply the same greedy selection rule: fill each array's n/2 capacity with elements that introduce new distinct values first. Sorting increases the cost to O(n log n), but it reduces reliance on extra memory. This approach fits environments where you want deterministic memory usage or when working within systems that already process sorted arrays.

The algorithm still relies on the same greedy reasoning: maximize distinct contributions early and only use shared values when necessary. Sorting simply replaces the hash-based uniqueness detection.

Recommended for interviews: The hash set greedy solution is the expected approach. It runs in O(n) time and clearly demonstrates understanding of array processing, set operations, and greedy optimization. A sorting-based solution shows solid reasoning but is usually considered slightly less optimal because of the extra log n factor.