Maximum Size of a Set After Removals solution and explanation
9 more videos on this problem
Maximum Size of a Set After Removals | Super Simple Solution | SetsAryan Mittal · 7:59 · 2K views
10037 Maximum Size of a Set After Removals || Set Intersection with Math 🔥Ayush Rao · 10:10 · 1K views
10037. Maximum Size of a Set After Removals | Weekly Leetcode 379codingMohan · 10:00 · 1K views
Leetcode Weekly contest 379 || Maximum size of a set After Removals|Minimum moves to Capture a QueenCode with HR · 0:15 · 1K views
3002. Maximum Size of a Set After Removals (Leetcode Medium)Programming Live with Larry · 11:36 · 497 views
Maximum Size of a Set After Removals | Set | Weekly 379Tech Courses · 12:56 · 220 views
Leetcode 3002: Maximum Size of a Set After Removals | Weekly ContestAlgorithms Casts · 17:02 · 216 views
Maximum Size of a Set After Removals | 10037Web Mickey · 22:13 · 159 views
LeetCode 10037 - Maximum Size of a Set After Removals - PythonAlpha-Code · 15:48 · 69 views
LeetCode Weekly 379 - Medium - 3002 Maximum Size of a Set After RemovalsLearn with EmKay · 15:58 · 48 views
The problem
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.length1 <= n <= 2 * 104nis 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.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print(arr)import java.util.Arrays;
class MergeSort {
void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
System.arraycopy(arr, l, L, 0, n1);
System.arraycopy(arr, m + 1, R, 0, n2);
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
new MergeSort().mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(std::vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.size() - 1);
for (int val : arr)
std::cout << val << " ";
return 0;
}function mergeSort(arr) {
if (arr.length < 2) return arr;
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
const arr = [12, 11, 13, 5, 6, 7];
console.log(mergeSort(arr));#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, arr_size - 1);
for (int i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
return 0;
}using System;
class Program {
static void Merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
Array.Copy(arr, l, L, 0, n1);
Array.Copy(arr, m + 1, R, 0, n2);
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
static void MergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
MergeSort(arr, l, m);
MergeSort(arr, m + 1, r);
Merge(arr, l, m, r);
}
}
static void Main() {
int[] arr = {12, 11, 13, 5, 6, 7};
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine(string.Join(" ", arr));
}
}The Python code efficiently implements merge sort using a recursive divide and conquer strategy. The array is partitioned into two halves, each of which is sorted and merged back together.
Time complexity: O(n log n); Space complexity: O(n) due to the recursive stack and temporary arrays used for merging.
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.
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickSortIterative(arr, l, h):
size = h - l + 1
stack = [0] * size
top = -1
top += 1
stack[top] = l
top += 1
stack[top] = h
while top >= 0:
h = stack[top]
top -= 1
l = stack[top]
top -= 1
p = partition(arr, l, h)
if p - 1 > l:
top += 1
stack[top] = l
top += 1
stack[top] = p - 1
if p + 1 < h:
top += 1
stack[top] = p + 1
top += 1
stack[top] = h
arr = [4, 2, 6, 9, 3]
quickSortIterative(arr, 0, len(arr) - 1)
print(arr)import java.util.Stack;
class IterativeQuickSort {
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
static void quickSortIterative(int[] arr, int l, int h) {
Stack<Integer> stack = new Stack<>();
stack.push(l);
stack.push(h);
while (!stack.isEmpty()) {
h = stack.pop();
l = stack.pop();
int p = partition(arr, l, h);
if (p - 1 > l) {
stack.push(l);
stack.push(p - 1);
}
if (p + 1 < h) {
stack.push(p + 1);
stack.push(h);
}
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 6, 9, 3};
quickSortIterative(arr, 0, arr.length - 1);
for (int value : arr) {
System.out.print(value + " ");
}
}
}#include <iostream>
#include <stack>
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSortIterative(int arr[], int l, int h) {
std::stack<int> stack;
stack.push(l);
stack.push(h);
while (!stack.empty()) {
h = stack.top(); stack.pop();
l = stack.top(); stack.pop();
int p = partition(arr, l, h);
if (p - 1 > l) {
stack.push(l);
stack.push(p - 1);
}
if (p + 1 < h) {
stack.push(p + 1);
stack.push(h);
}
}
}
int main() {
int arr[] = {4, 2, 6, 9, 3};
int n = sizeof(arr) / sizeof(arr[0]);
quickSortIterative(arr, 0, n - 1);
for (int i = 0; i < n; i++)
std::cout << arr[i] << " ";
return 0;
}function partition(arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
function quickSortIterative(arr, low, high) {
let stack = [];
stack.push({x: low, y: high});
while (stack.length) {
const {x, y} = stack.pop();
high = y;
low = x;
let p = partition(arr, low, high);
if (p - 1 > low) stack.push({x: low, y: p - 1});
if (p + 1 < high) stack.push({x: p + 1, y: high});
}
}
const arr = [4, 2, 6, 9, 3];
quickSortIterative(arr, 0, arr.length - 1);
console.log(arr);#include <stdio.h>
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void quickSortIterative(int arr[], int l, int h) {
int stack[h - l + 1];
int top = -1;
stack[++top] = l;
stack[++top] = h;
while (top >= 0) {
h = stack[top--];
l = stack[top--];
int p = partition(arr, l, h);
if (p - 1 > l) {
stack[++top] = l;
stack[++top] = p - 1;
}
if (p + 1 < h) {
stack[++top] = p + 1;
stack[++top] = h;
}
}
}
int main() {
int arr[] = {4, 2, 6, 9, 3};
int n = sizeof(arr) / sizeof(arr[0]);
quickSortIterative(arr, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}using System;
using System.Collections.Generic;
class IterativeQuickSort {
static int Partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp1 = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp1;
return i + 1;
}
static void QuickSortIterative(int[] arr, int l, int h) {
Stack<int> stack = new Stack<int>();
stack.Push(l);
stack.Push(h);
while (stack.Count > 0) {
h = stack.Pop();
l = stack.Pop();
int p = Partition(arr, l, h);
if (p - 1 > l) {
stack.Push(l);
stack.Push(p - 1);
}
if (p + 1 < h) {
stack.Push(p + 1);
stack.Push(h);
}
}
}
static void Main() {
int[] arr = {4, 2, 6, 9, 3};
QuickSortIterative(arr, 0, arr.Length - 1);
Console.WriteLine(string.Join(" ", arr));
}
}Python's iterative QuickSort avoids recursive stack overflow by utilizing a manually controlled stack for pivot-based array partitioning.
Best and average time complexity: O(n log n); worst-case can reach O(n^2). Space complexity is O(log n) with stack usage.
Approach 3: Default Approach
function maximumSetSize(nums1: number[], nums2: number[]): number {
const s1: Set<number> = new Set(nums1);
const s2: Set<number> = new Set(nums2);
const n = nums1.length;
let [a, b, c] = [0, 0, 0];
for (const x of s1) {
if (!s2.has(x)) {
++a;
}
}
for (const x of s2) {
if (!s1.has(x)) {
++b;
} else {
++c;
}
}
a = Math.min(a, n >> 1);
b = Math.min(b, n >> 1);
return Math.min(a + b + c, n);
}func maximumSetSize(nums1 []int, nums2 []int) int {
s1 := map[int]bool{}
s2 := map[int]bool{}
for _, x := range nums1 {
s1[x] = true
}
for _, x := range nums2 {
s2[x] = true
}
a, b, c := 0, 0, 0
for x := range s1 {
if !s2[x] {
a++
}
}
for x := range s2 {
if !s1[x] {
b++
} else {
c++
}
}
n := len(nums1)
a = min(a, n/2)
b = min(b, n/2)
return min(a+b+c, n)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Divide and Conquer | Time complexity: O(n log n); Space complexity: O(n) due to the recursive stack and temporary arrays used for merging. |
| Iterative Sorting: QuickSort | Best and average time complexity: O(n log n); worst-case can reach O(n^2). Space complexity is O(log n) with stack usage. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Hash Sets | O(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) extra | Useful when minimizing auxiliary memory or when arrays are already sorted. |
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.