#3002

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Size of a Set After Removals

Maximize a set size by strategically removing half of elements from two arrays using hash lookups and array scanning.

Problem Statement

You are given two integer arrays nums1 and nums2 of equal even length n. You must remove exactly n / 2 elements from each array and then insert the remaining elements from both arrays into a set s.

Return the maximum possible size of s after these removals. The goal is to keep the most unique numbers, using a strategy based on array scanning and hash lookups to decide which elements to remove.

Examples

Example 1

Input: nums1 = [1,2,1,2], nums2 = [1,1,1,1]

Output: 2

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

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

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

Solution Approach

Count element frequencies

Use hash tables to record the frequency of each number in both nums1 and nums2. This allows efficient determination of which elements are most repeated and which contribute most to the set.

Greedy removal of duplicates

Iterate over nums1 and nums2, removing n / 2 elements from each array. Prioritize removing elements that appear more frequently to maximize the number of unique elements left in the set.

Combine remaining elements into set

After removals, insert the remaining elements of nums1 and nums2 into a set s. The set size after these operations is the answer, as hash lookup ensures duplicates are counted only once and array scanning ensures optimal removals.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) due to single passes over arrays for counting and removal using hash tables. Space complexity is O(n) for storing frequencies and the resulting set.

What Interviewers Usually Probe

The candidate immediately counts frequencies to identify high-occurrence elements.
Candidate uses a greedy strategy to remove duplicates rather than random selection.
They combine remaining elements into a set and justify that this yields maximum size.

Common Pitfalls or Variants

Common pitfalls

Removing elements without considering frequency can reduce unique set size.
Miscounting n / 2 removals leads to incorrect final set size.
Failing to use hash lookup may result in duplicate elements inflating perceived set size.

Follow-up variants

Change removal strategy to minimize sum instead of maximizing set size.
Arrays contain negative numbers and zeros affecting hash table keys.
Arrays have different lengths, requiring adjustment to removal count and greedy logic.

FAQ

How does this problem use array scanning and hash lookup pattern?

You scan both arrays to track occurrences while using hash tables to quickly determine which elements can be removed to maximize unique set size.

What is the strategy to maximize the set size?

Count frequencies, remove the most repeated elements greedily, and then combine remaining elements into a set.

Can nums1 and nums2 contain duplicates?

Yes, duplicates exist and must be managed with hash lookups to ensure the resulting set counts each value once.

Why must n be even in this problem?

An even length ensures exactly n / 2 elements can be removed from each array without fractional counts.

Is there a more efficient way than brute force removal?

Yes, using hash tables for frequency counting and greedy removal achieves O(n) time without exploring all removal combinations.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

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)

Continue Practicing

#3035 maximum palindromes after operations #2910 minimum number of groups to create a valid assignment #2897 apply operations on array to maximize sum of squares