Skip to main content

Hashing

Maximum Size of a Set After Removals Solution In C++/Java/Python/JS

Problem Description

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.

Examples:

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.

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.

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 2 * 104
  • n is even.
  • 1 <= nums1[i], nums2[i] <= 109
💡
Try it Yourself First!
This problem involves removing elements from two equal-length arrays while ensuring that no element appears in both. The core challenge is to determine the largest possible size of the remaining unique elements. A key insight is to focus on the frequency of elements and find the most common ones, as they limit removals. The optimal approach involves calculating the maximum frequency and balancing the deletions to maximize the unique set size efficiently.

Brute Force Approach

Intuition

To understand this problem, start by recognizing that we have two arrays, nums1 and nums2, each containing n elements. The goal is to determine the maximum possible size of a set after removing one element (from both arrays at the same index). A "set" only keeps unique elements, so our aim is to maximize the number of distinct elements remaining.

A simple way to approach the problem is by iterating over each index and temporarily removing that element from both arrays. For each removal, we insert the remaining elements into a set, which automatically filters out duplicates. The size of this set tells us how many distinct numbers are left after removing one element. By repeating this process for every possible removal, we determine the maximum size we can achieve.

iterates over every index i, creates a new set for every case, and adds all remaining numbers from both arrays into it. The highest recorded set size across all iterations becomes our answer. While this method is easy to understand and implement, it is inefficient because it repeats operations for each possible removal.

Approach

Step 1: Initialize Variables

  • Create a variable maxSize to track the maximum distinct set size found so far.
  • Get the total number of elements, n, from the input arrays nums1 and nums2.

Step 2: Iterate Over Each Index

  • Loop through each index i in the range [0, n-1].
  • At each step, assume we remove the element at index i from both nums1 and nums2.

Step 3: Create a Set for Remaining Elements

  • Use a set data structure to store the unique numbers left after removal.
  • Insert all elements from nums1 except nums1[i].
  • Insert all elements from nums2 except nums2[i].

Step 4: Update Maximum Size

  • Check the size of the set and update maxSize if the new size is larger.

Step 5: Return the Maximum Size Found

  • After iterating through all possible removals, return the maxSize value.

Maximum Size of a Set After Removals Game Dry run - BruteForce

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

Step-by-Step Execution:
We iterate over each index i from 0 to 3, removing nums1[i] and nums2[i] and computing the size of the remaining unique elements.
Iteration 1 (i = 0)
Elements Removed: nums1[0] = 1, nums2[0] = 1
Remaining Elements:
nums1 = [2, 1, 2]
nums2 = [1, 1, 1]
Unique Elements After Removal: {2, 1}
Size = 2
Update: maxSize = max(0, 2) = 2
Iteration 2 (i = 1)
Elements Removed: nums1[1] = 2, nums2[1] = 1
Remaining Elements:
nums1 = [1, 2]
nums2 = [1, 1]
Unique Elements After Removal: {1, 2}
Size = 2
Update: maxSize remains 2
Iteration 3 (i = 2)
Elements Removed: nums1[2] = 1, nums2[2] = 1
Remaining Elements:
nums1 = [2, 2]
nums2 = [1, 1]
Unique Elements After Removal: {1, 2}
Size = 2
Update: maxSize remains 2
Iteration 4 (i = 3)
Elements Removed: nums1[3] = 2, nums2[3] = 1
Remaining Elements:
nums1 = [1, 2, 1]
nums2 = [1, 1, 1]
Unique Elements After Removal: {1, 2}
Size = 2
Final Answer: maxSize = 2

Maximum Size of a Set After Removals Code for All Languages - BruteForce
C++ 
class Solution {
public:
    int maxSizeAfterRemovals(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> uniqueSet;
        int n = nums1.size();

        // Try removing each possible element and check the remaining unique set size
        int maxSize = 0;

        for (int i = 0; i < n; i++) {
            unordered_set<int> tempSet;
            
            // Insert elements from both arrays except the i-th index
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    tempSet.insert(nums1[j]);
                    tempSet.insert(nums2[j]);
                }
            }

            // Update the max possible set size
            maxSize = max(maxSize, (int)tempSet.size());
        }

        return maxSize;
    }
};

Maximum Size of a Set After Removals code in Java - BruteForce 
import java.util.*;

class Solution {
    public int maxSizeAfterRemovals(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int maxSize = 0;

        // Iterate over each index to remove one element
        for (int i = 0; i < n; i++) {
            Set<Integer> tempSet = new HashSet<>();

            // Add remaining elements from both arrays to the set
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    tempSet.add(nums1[j]);
                    tempSet.add(nums2[j]);
                }
            }

            // Update the maximum size of the unique set
            maxSize = Math.max(maxSize, tempSet.size());
        }

        return maxSize;
    }
}

Maximum Size of a Set After Removals code in Python - BruteForce 
from typing import List

class Solution:
    def maxSizeAfterRemovals(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        max_size = 0

        # Iterate over each index to remove one element
        for i in range(n):
            temp_set = set()

            # Add remaining elements from both arrays to the set
            for j in range(n):
                if j != i:
                    temp_set.add(nums1[j])
                    temp_set.add(nums2[j])

            # Update the maximum size of the unique set
            max_size = max(max_size, len(temp_set))

        return max_size

Maximum Size of a Set After Removals code in Javascript - BruteForce 
class Solution {
    maxSizeAfterRemovals(nums1, nums2) {
        let n = nums1.length;
        let maxSize = 0;

        // Iterate over each index to remove one element
        for (let i = 0; i < n; i++) {
            let tempSet = new Set();

            // Add remaining elements from both arrays to the set
            for (let j = 0; j < n; j++) {
                if (j !== i) {
                    tempSet.add(nums1[j]);
                    tempSet.add(nums2[j]);
                }
            }

            // Update the maximum size of the unique set
            maxSize = Math.max(maxSize, tempSet.size);
        }

        return maxSize;
    }
}

Time Complexity: O(n2)

The code iterates through nums1 and nums2 of size n, removing one element pair at a time.
For each removal, it recalculates the unique elements in the remaining list, which takes O(n) time.
Since this process is repeated for all n elements, the total time complexity is O(n²).

Space Complexity:O(n)

Auxiliary Space Complexity

  • The algorithm uses a set to store unique elements, which at most holds n elements. This takes O(n) space.
  • Other variables such as maxSize, loop variables, and counters take O(1) space.
  • Thus, the auxiliary space complexity is O(n).

Total Space Complexity

  • The input arrays nums1 and nums2 already take O(n) space.
  • Adding the auxiliary space O(n), the total space complexity remains O(n).

Optimal Approach

Intuition

The problem asks us to maximize the number of distinct elements we can select while ensuring that at most n/2 elements come from each array. This immediately suggests that we should focus on unique elements in each array and how they overlap.

A natural way to approach this is by categorizing the elements based on their presence in the two arrays. Some elements are exclusive to nums1, some are exclusive to nums2, and some appear in both. Understanding this classification helps us prioritize selection: we first pick as many unique elements as possible from each array, and if there’s still room, we fill the remaining space with elements that appear in both.

The next thought is about constraints—since we can take at most n/2 elements from each array, we should first ensure we take all distinct elements up to this limit. If there aren’t enough unique elements, we must use elements common to both arrays to reach the required count. This leads to a greedy approach where we maximize selections from exclusive elements first and then compensate with shared elements.

Finally, by iterating through the maps and adjusting counts accordingly, we ensure that we respect the constraints while maximizing our selection. This structured way of thinking—breaking elements into categories, setting limits, and then filling gaps—leads naturally to the implementation of the code.

Approach

Step 1: Initialize Frequency Maps
Create two unordered maps, m1 and m2, to count the occurrences of each element in nums1 and nums2. Iterate through nums1 and nums2, updating the frequency count for each element.
Initialize three integer variables:

  • only_in_1 to count elements that appear only in nums1
  • only_in_2 to count elements that appear only in nums2
  • both to count elements that appear in both arrays

Step 2: Categorize Elements
Iterate through m1. If an element is also found in m2, increment both. Otherwise, increment only_in_1.
Similarly, iterate through m2. If an element is not found in m1, increment only_in_2.

Step 3: Limit only_in_1 and only_in_2
Each of these counts should not exceed n/2, as we are allowed to take at most n/2 unique elements from each array. If only_in_1 is greater than n/2, set it to n/2. Do the same for only_in_2.

Step 4: Adjust Using both
If only_in_1 is less than n/2, find the number of additional elements needed to reach n/2. Take this number from both, updating both accordingly. Repeat this process for only_in_2.

Step 5: Return the Final Count
The final answer is the sum of only_in_1 and only_in_2, as this represents the maximum number of unique elements we can include while following the constraints.

Maximum Size of a Set After Removals Dry run - Optimised

Input:
nums1 = [1, 2, 1, 2]
nums2 = [1, 1, 1, 1]
n = 4 (length of nums1 and nums2)

Step 1: Count Frequency of Elements

Using hash maps:
m1 (Frequency of elements in nums1) → {1: 2, 2: 2}
m2 (Frequency of elements in nums2) → {1: 4}

Step 2: Identify Element Categories
only_in_1 (Elements in nums1 but not in nums2) → {2} appears only in nums1, so only_in_1 = 1
only_in_2 (Elements in nums2 but not in nums1) → No elements in nums2 are absent in nums1, so only_in_2 = 0
both (Elements in both nums1 and nums2) → {1} appears in both arrays, so both = 1

Step 3: Limit Unique Elements to n/2
n/2 = 2
only_in_1 = min(1, 2) = 1
only_in_2 = min(0, 2) = 0

Step 4: Fill Missing Elements from both
only_in_1 is 1 but can go up to 2.
needed elements = 2 - 1 = 1
available in both = 1
take 1 from both → now only_in_1 = 2 and both = 0
only_in_2 is 0 but can go up to 2.
needed elements = 2 - 0 = 2
available in both = 0
no elements left in both, so no change in only_in_2

Step 5: Compute the Final Answer
only_in_1 + only_in_2 = 2 + 0 = 2
Final Answer: 2

Maximum Size of a Set After Removals for All Languages - Optimised
C++ 
class Solution {
public:
    int maximumSetSize(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        unordered_map<int, int> m1, m2;

        // Count frequency of elements in nums1
        for (auto i : nums1) m1[i]++;

        // Count frequency of elements in nums2
        for (auto i : nums2) m2[i]++;

        int only_in_1 = 0, only_in_2 = 0, both = 0;

        // Count elements only in nums1 and elements in both arrays
        for (auto& i : m1) {
            if (m2.find(i.first) != m2.end()) both++;
            else only_in_1++;
        }

        // Count elements only in nums2
        for (auto& i : m2) {
            if (m1.find(i.first) == m1.end()) only_in_2++;
        }

        // Limit the count of unique elements to n/2
        only_in_1 = min(only_in_1, n / 2);
        only_in_2 = min(only_in_2, n / 2);

        // Fill up missing unique elements from "both" category
        if (only_in_1 < n / 2) {
            int req = n / 2 - only_in_1;
            int has = min(req, both);
            both -= has;
            only_in_1 += has;
        }

        if (only_in_2 < n / 2) {
            int req = n / 2 - only_in_2;
            int has = min(req, both);
            both -= has;
            only_in_2 += has;
        }

        // Return the maximum set size
        return only_in_1 + only_in_2;
    }
};

Maximum Size of a Set After Removals Code in Java - Optimised 
import java.util.HashMap;

class Solution {
    public int maximumSetSize(int[] nums1, int[] nums2) {
        int n = nums1.length;
        HashMap<Integer, Integer> m1 = new HashMap<>();
        HashMap<Integer, Integer> m2 = new HashMap<>();

        // Count frequency of elements in nums1
        for (int num : nums1) m1.put(num, m1.getOrDefault(num, 0) + 1);

        // Count frequency of elements in nums2
        for (int num : nums2) m2.put(num, m2.getOrDefault(num, 0) + 1);

        int only_in_1 = 0, only_in_2 = 0, both = 0;

        // Count elements only in nums1 and elements in both arrays
        for (int key : m1.keySet()) {
            if (m2.containsKey(key)) both++;
            else only_in_1++;
        }

        // Count elements only in nums2
        for (int key : m2.keySet()) {
            if (!m1.containsKey(key)) only_in_2++;
        }

        // Limit the count of unique elements to n/2
        only_in_1 = Math.min(only_in_1, n / 2);
        only_in_2 = Math.min(only_in_2, n / 2);

        // Fill up missing unique elements from "both" category
        if (only_in_1 < n / 2) {
            int req = n / 2 - only_in_1;
            int has = Math.min(req, both);
            both -= has;
            only_in_1 += has;
        }

        if (only_in_2 < n / 2) {
            int req = n / 2 - only_in_2;
            int has = Math.min(req, both);
            both -= has;
            only_in_2 += has;
        }

        // Return the maximum set size
        return only_in_1 + only_in_2;
    }
}

Maximum Size of a Set After Removals Code in Python - Optimised 
from collections import Counter

class Solution:
    def maximumSetSize(self, nums1: list[int], nums2: list[int]) -> int:
        n = len(nums1)

        # Count frequency of elements in nums1 and nums2
        m1 = Counter(nums1)
        m2 = Counter(nums2)

        # Count elements only in nums1, only in nums2, and in both
        only_in_1 = sum(1 for num in m1 if num not in m2)
        only_in_2 = sum(1 for num in m2 if num not in m1)
        both = sum(1 for num in m1 if num in m2)

        # Limit the count of unique elements to n/2
        only_in_1 = min(only_in_1, n // 2)
        only_in_2 = min(only_in_2, n // 2)

        # Fill up missing unique elements from "both" category
        if only_in_1 < n // 2:
            req = n // 2 - only_in_1
            has = min(req, both)
            both -= has
            only_in_1 += has

        if only_in_2 < n // 2:
            req = n // 2 - only_in_2
            has = min(req, both)
            both -= has
            only_in_2 += has

        # Return the maximum set size
        return only_in_1 + only_in_2

Maximum Size of a Set After Removals Code in Javascript - Optimised 
class Solution {
    maximumSetSize(nums1, nums2) {
        let n = nums1.length;
        let m1 = new Map(), m2 = new Map();

        // Count frequency of elements in nums1
        for (let num of nums1) m1.set(num, (m1.get(num) || 0) + 1);

        // Count frequency of elements in nums2
        for (let num of nums2) m2.set(num, (m2.get(num) || 0) + 1);

        let only_in_1 = 0, only_in_2 = 0, both = 0;

        // Count elements only in nums1 and elements in both arrays
        for (let [key, _] of m1) {
            if (m2.has(key)) both++;
            else only_in_1++;
        }

        // Count elements only in nums2
        for (let [key, _] of m2) {
            if (!m1.has(key)) only_in_2++;
        }

        // Limit the count of unique elements to n/2
        only_in_1 = Math.min(only_in_1, Math.floor(n / 2));
        only_in_2 = Math.min(only_in_2, Math.floor(n / 2));

        // Fill up missing unique elements from "both" category
        if (only_in_1 < Math.floor(n / 2)) {
            let req = Math.floor(n / 2) - only_in_1;
            let has = Math.min(req, both);
            both -= has;
            only_in_1 += has;
        }

        if (only_in_2 < Math.floor(n / 2)) {
            let req = Math.floor(n / 2) - only_in_2;
            let has = Math.min(req, both);
            both -= has;
            only_in_2 += has;
        }

        // Return the maximum set size
        return only_in_1 + only_in_2;
    }
}

Time Complexity: O(n)

Time Complexity Analysis
The code consists of several steps, each contributing to the overall complexity.
Building Frequency Maps (m1 and m2)

    • We iterate through nums1 and nums2, inserting elements into unordered_map.
    • Each insertion takes O(1) on average, and since we iterate n elements in both arrays, this step is O(n) in total.

Counting Unique and Common Elements

    • We iterate through m1 and check whether each element is in m2.
    • This takes O(n) in the worst case if all elements are unique.
    • Similarly, iterating through m2 takes another O(n).
    • This step is O(n) + O(n) = O(n) in total.

Adjusting Counts (only_in_1, only_in_2, both)
These are simple arithmetic operations and comparisons, which take O(1) time.

Total Time Complexity
All operations combined result in an overall time complexity of O(n).

Space Complexity: O(n)

Auxiliary Space Complexity (Extra Space Used)
Unordered Maps (m1 and m2)

    • Each map stores unique elements of nums1 and nums2.
    • In the worst case (all elements unique), each map stores O(n) elements.
    • Since each map takes O(n) space, the total space for maps is O(n) + O(n) = O(n).

Integer Variables (only_in_1, only_in_2, both) , These require O(1) space.

Total auxiliary space complexity: O(n)

Total Space Complexity (Including Input Storage)
Input Arrays (nums1 and nums2)
These are given as input and require O(n) + O(n) = O(n) space.

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Intersection of Two Arrays

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be uniqueand you may return the result in any order.