Problem Statement

You are given an integer array nums of even length. You have to split the array into two parts nums1 and nums2 such that:

• nums1.length == nums2.length == nums.length / 2.
• nums1 should contain distinct elements.
• nums2 should also contain distinct elements.

Return true if it is possible to split the array, and false otherwise.

Examples

Example 1:

Input: nums = [1, 1, 2, 2, 3, 4]
Output: true

Explanation:
One of the possible ways to split nums is nums1 = [1, 2, 3] and nums2 = [1, 2, 4]

Example 2:

Input: nums = [1, 1, 1, 1]
Output: false

Explanation: The only possible way to split the nums is nums1 = [1, 1] and nums2 = [1, 1]. Both nums1 and nums2 do not contain distinct elements. Therefore, we return false.

Different Approaches

1️⃣ Hashing

Intuition:

As we know that the array given is of even length, we have to split it into two equal parts. We have to determine the conditions under which it's not possible to create two arrays satisfying the given conditions, rather than focusing on the lengths of the two arrays.

Consider the example:

nums = [1, 1, 2, 2, 3, 4]

Based on the description, we can create:

nums1 = [1, 2, 3]
nums2 = [1, 2, 4]

Here, we can observe that every elements either have the frequency 1 or 2.

Let's add new numbers, 1 and 5.

nums = [1, 1, 2, 2, 3, 4, 1, 5]

In the previous answer we can add 1, either of them and 5 either of them.

nums1 = [1, 2, 3, 5]
nums2 = [1, 2, 4, 1], 1 = duplicate

or

nums1 = [1, 2, 3, 1], 1 = duplicate
nums2 = [1, 2, 4, 5]

We found out that the in whoever we add the 1 that subarray contains the duplicate numbers.

Thus in this array 1 has the frequency of 2. So, we can build an intuition that we can divide the array into two of equal parts if every members has the frequency either 1 or 2.

Code:

class Solution {
public:
    bool isPossibleToSplit(vector<int>& nums) {
        // Step 1: Create a frequency map to count the occurrences of each number in the array.
        unordered_map<int, int> freq; // Maps each number to its frequency.
        for (int i = 0; i < nums.size(); i++) {
            freq[nums[i]]++; // Increment the count for the current number.
        }

        // Step 2: Iterate through the frequency map to check if any number appears more than twice.
        for (auto [number, frequency] : freq) { // Structured binding: unpack number and frequency.
            if (frequency > 2) { 
                // If any number appears more than twice, it's not possible to split.
                return false;
            }
        }

        // Step 3: If no number appears more than twice, return true.
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(n), where n is the number of elements of the array.
• Space Complexity: O(n)