Is Maximum Size of a Set After Removals easy or hard?

The problem is rated Medium because the greedy reasoning is not immediately obvious. Once you recognize that maximizing distinct elements requires prioritizing values unique to each array, the implementation becomes straightforward.

Maximum Size of a Set After Removals Python/Java solution

Most implementations use sets in Python or HashSet in Java. The algorithm builds two sets, computes unique and shared values, then greedily selects elements while respecting the n/2 removal constraint for each array.

How to solve Maximum Size of a Set After Removals in O(n)?

Use hash sets to track distinct elements in both arrays. Compute elements unique to each array and elements that appear in both. Fill each array's allowed n/2 capacity with unique-only values first, then use remaining slots for shared values. Set operations and constant-time lookups keep the algorithm linear.

What is the best approach for Maximum Size of a Set After Removals?

The optimal solution uses a greedy strategy with hash sets. Convert both arrays to sets, separate elements into unique and common groups, and prioritize keeping elements that appear in only one array. This ensures the distinct count grows as quickly as possible. The algorithm runs in O(n) time with O(n) space.

Is Maximum Size of a Set After Removals asked at Google/Amazon/Meta?

Greedy and hash-set problems similar to this frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests reasoning about distinct elements, set operations, and capacity constraints, which are common themes in real interview questions.

What data structure is used in Maximum Size of a Set After Removals?

The main data structure is a hash set. It allows O(1) average-time insertion and lookup, which is essential for tracking unique elements and computing intersections between the two arrays efficiently.

What is the time complexity of Maximum Size of a Set After Removals?

The optimal hash-set solution runs in O(n) time because each element is processed a constant number of times when building sets and computing intersections. Space complexity is O(n) due to storing distinct values. A sorting-based alternative runs in O(n log n) time.

Description Hints 3 Solution Video 7:59

3002. Maximum Size of a Set After Removals

Medium46.2% acceptance2 companies

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.

Return the maximum possible size of the set s.

Example 1:

Input: nums1 = [1,2,1,2], nums2 = [1,1,1,1]
Output: 2
Explanation: 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
Explanation: 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
Explanation: 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 * 10⁴
n is even.
1 <= nums1[i], nums2[i] <= 10⁹

Asked at 2 companies

Microsoft Amazon

Topics

Hints open one at a time

Hint 1

Removing n / 2 elements from each array is the same as keeping n / 2 elements in each array.

Hint 2

Think of a greedy algorithm.

Hint 3

For each array, we will greedily keep the elements that are only in that array. Once we run out of such elements, we will keep the elements that are common to both arrays.

7:59

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution