Skip to main content
Talentd

Maximum Size of a Set After Removals - Solution & Explanation

MediumArrayHash TableGreedy16 min readAsked at: Amazon, Microsoft
Practice this problem

Problem Statement

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 * 104
  • n is even.
  • 1 <= nums1[i], nums2[i] <= 109

Approach Overview

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.

Approach 1: Divide and Conquer

This approach involves dividing the problem into smaller subproblems, solving each subproblem independently, and then combining the results to solve the original problem. This technique is particularly useful for problems that can be divided into similar subproblems, such as sorting algorithms.

The above solution implements the Merge Sort algorithm using the Divide and Conquer approach. The array is divided into two halves, which are recursively sorted and then merged.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity of Merge Sort is O(n log n) due to the division and merging of array elements, and the space complexity is O(n) because it requires additional space to store the temporary arrays.

Try this approach in the editor →

Approach 2: Iterative Sorting: QuickSort

An iterative approach to QuickSort often uses a stack to simulate the implicit recursion stack. This method avoids stack overflow issues found in recursive implementations for large datasets. It sorts by partitioning the data around a pivot point.

The solution implements an iterative QuickSort using a stack to replace the system’s call stack. This eliminates recursion-related depth issues. It partitions the array using a pivot and manages indices manually.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time: O(n^2) worst-case (though O(n log n) average); Space: O(log n) due to stack use for indices.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Divide and Conquer

The time complexity of Merge Sort is O(n log n) due to the division and merging of array elements, and the space complexity is O(n) because it requires additional space to store the temporary arrays.

Iterative Sorting: QuickSort

Time: O(n^2) worst-case (though O(n log n) average); Space: O(log n) due to stack use for indices.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Hash SetsO(n)O(n)Best general solution when hash tables are allowed and you want optimal linear performance.
Sorting + Greedy Scan (QuickSort)O(n log n)O(1) extraUseful when minimizing auxiliary memory or when arrays are already sorted.

Video Solution

Maximum Size of a Set After Removals | Super Simple Solution | Sets • Aryan Mittal • 2,341 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Maximum Size of a Set After Removals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Intersection of Two Arrays