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 themaximum possible size of the set s.

Examples

Example 1

1
2
3
4
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

1
2
3
4
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

1
2
3
4
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^4
  • n is even.
  • 1 <= nums1[i], nums2[i] <= 10^9

Solution

Method 1 – Greedy with Frequency Counting

Intuition

To maximize the size of the set after removals, we want to keep as many unique elements as possible. Since we must remove exactly half from each array, we should prioritize keeping unique elements from both arrays, avoiding overlap where possible.

Approach

  1. Count the frequency of each number in both arrays.
  2. Let k = n // 2 (number of elements to keep from each array).
  3. For all possible splits of unique elements between the two arrays, try to maximize the number of unique elements in the final set.
  4. The answer is the minimum of 2 * k and the total number of unique elements in the union of both arrays.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int maximumSetSize(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), k = n / 2;
        unordered_set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end());
        int both = 0;
        for (int x : s1) if (s2.count(x)) both++;
        int only1 = s1.size() - both, only2 = s2.size() - both;
        int ans = min(2 * k, only1 + only2 + min(both, k));
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maximumSetSize(nums1, nums2 []int) int {
    n, k := len(nums1), len(nums1)/2
    s1, s2 := map[int]struct{}{}, map[int]struct{}{}
    for _, x := range nums1 { s1[x] = struct{}{} }
    for _, x := range nums2 { s2[x] = struct{}{} }
    both := 0
    for x := range s1 { if _, ok := s2[x]; ok { both++ } }
    only1 := len(s1) - both
    only2 := len(s2) - both
    ans := only1 + only2 + min(both, k)
    if ans > 2*k { ans = 2 * k }
    return ans
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int maximumSetSize(int[] nums1, int[] nums2) {
        int n = nums1.length, k = n / 2;
        Set<Integer> s1 = new HashSet<>();
        Set<Integer> s2 = new HashSet<>();
        for (int x : nums1) s1.add(x);
        for (int x : nums2) s2.add(x);
        int both = 0;
        for (int x : s1) if (s2.contains(x)) both++;
        int only1 = s1.size() - both, only2 = s2.size() - both;
        int ans = only1 + only2 + Math.min(both, k);
        return Math.min(ans, 2 * k);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    fun maximumSetSize(nums1: IntArray, nums2: IntArray): Int {
        val n = nums1.size; val k = n / 2
        val s1 = nums1.toSet(); val s2 = nums2.toSet()
        val both = s1.count { it in s2 }
        val only1 = s1.size - both; val only2 = s2.size - both
        val ans = only1 + only2 + minOf(both, k)
        return minOf(ans, 2 * k)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maximumSetSize(self, nums1: list[int], nums2: list[int]) -> int:
        n = len(nums1)
        k = n // 2
        s1 = set(nums1)
        s2 = set(nums2)
        both = len(s1 & s2)
        only1 = len(s1) - both
        only2 = len(s2) - both
        ans = only1 + only2 + min(both, k)
        return min(ans, 2 * k)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn maximum_set_size(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let k = n / 2;
        let s1: std::collections::HashSet<_> = nums1.iter().cloned().collect();
        let s2: std::collections::HashSet<_> = nums2.iter().cloned().collect();
        let both = s1.intersection(&s2).count();
        let only1 = s1.len() - both;
        let only2 = s2.len() - both;
        let ans = only1 + only2 + std::cmp::min(both, k);
        ans.min(2 * k) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    maximumSetSize(nums1: number[], nums2: number[]): number {
        const n = nums1.length, k = n / 2;
        const s1 = new Set(nums1), s2 = new Set(nums2);
        let both = 0;
        for (const x of s1) if (s2.has(x)) both++;
        const only1 = s1.size - both, only2 = s2.size - both;
        let ans = only1 + only2 + Math.min(both, k);
        return Math.min(ans, 2 * k);
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we scan both arrays and use set operations.
  • 🧺 Space complexity: O(n), for the sets used to track unique elements.