Maximum Size of a Set After Removals - Practice Coding Problems

Maximum Size of a Set After Removals - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [1,2,3,4], nums2 = [3,4,5,6]

› Output: 4

💡 Note: Remove [3,4] from nums1 and [3,4] from nums2. Remaining: [1,2] and [5,6]. Final set: {1,2,5,6} has size 4.

Example 2 — All Common Elements

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

› Output: 2

💡 Note: Remove duplicates optimally. Keep [1,2] from nums1 and [1] from nums2. Final set: {1,2} has size 2.

Example 3 — No Common Elements

$ Input: nums1 = [1,1,2,2], nums2 = [3,3,4,4]

› Output: 4

💡 Note: No overlap between arrays. Keep [1,2] from nums1 and [3,4] from nums2. Final set: {1,2,3,4} has size 4.

Constraints

n == nums1.length == nums2.length
1 ≤ n ≤ 10⁵
n is even
1 ≤ nums1[i], nums2[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays of length n, must remove n/2 from each

Optimal Removal

Remove duplicates and minimize overlap between arrays

Final Set

Combine remaining elements into a set for maximum size

Key Takeaway

🎯 Key Insight: Categorize elements into unique and common groups, then greedily select to minimize overlap

Asked in

M Meta 35 G Google 28 a Amazon 22

The key insight is to categorize elements into three groups: only in nums1, only in nums2, and common to both. The optimal strategy is to greedily keep unique elements first, then handle common elements to minimize overlap. Best approach is the Optimal Greedy Strategy with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(C(n,n/2)²)	O(n)	Generate all possible ways to remove n/2 elements from each array and find maximum set size
Frequency Count with Greedy Selection	O(n)	O(n)	Count element frequencies, then greedily select elements to maximize final set size
Optimal Greedy Strategy	O(n)	O(n)	Use mathematical insight to directly calculate maximum set size without enumeration

Brute Force - Try All Combinations — Algorithm Steps

Generate all combinations of n/2 elements to remove from nums1
Generate all combinations of n/2 elements to remove from nums2
For each combination pair, create set from remaining elements
Return maximum set size found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all ways to remove n/2 elements from each array

Test Each Pair

For each combination pair, merge remaining elements

Find Maximum

Track the largest set size across all combinations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* nums1, int* nums2, int n) {
    // Simplified brute force for small inputs only
    int half = n / 2;
    int maxSize = 0;
    
    // For demonstration with small arrays only
    if (n <= 4) {
        // Try keeping different combinations
        int used[1000] = {0};
        int count = 0;
        
        // Keep first half of each array
        for (int i = 0; i < half; i++) {
            if (!used[nums1[i] + 500]) {
                used[nums1[i] + 500] = 1;
                count++;
            }
            if (!used[nums2[i] + 500]) {
                used[nums2[i] + 500] = 1;
                count++;
            }
        }
        maxSize = max(maxSize, count);
        
        // Reset and try other combinations
        memset(used, 0, sizeof(used));
        count = 0;
        
        // Keep second half of each array
        for (int i = half; i < n; i++) {
            if (!used[nums1[i] + 500]) {
                used[nums1[i] + 500] = 1;
                count++;
            }
            if (!used[nums2[i] + 500]) {
                used[nums2[i] + 500] = 1;
                count++;
            }
        }
        maxSize = max(maxSize, count);
    }
    
    return maxSize > 0 ? maxSize : half; // Return reasonable default
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple parsing for small arrays
    int nums1[100], nums2[100];
    int n = 0;
    
    // Parse first array
    char* token = strtok(line1, "[],\n ");
    while (token != NULL && n < 100) {
        nums1[n] = atoi(token);
        token = strtok(NULL, "[],\n ");
        n++;
    }
    
    // Parse second array
    int idx = 0;
    token = strtok(line2, "[],\n ");
    while (token != NULL && idx < n) {
        nums2[idx] = atoi(token);
        token = strtok(NULL, "[],\n ");
        idx++;
    }
    
    printf("%d\n", solution(nums1, nums2, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(n,n/2)²)

Generate C(n,n/2) combinations for each array, where C(n,n/2) can be exponentially large

✓ Linear Growth

Space Complexity

O(n)

Store combinations and temporary sets

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler