Problem

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, andfalse otherwise .

Examples

Example 1

1
2
3

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

1
2
3

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

Constraints

  • 1 <= nums.length <= 100
  • nums.length % 2 == 0
  • 1 <= nums[i] <= 100

Solution

Method 1 – Frequency Count and Pigeonhole Principle

Intuition

If any number appears more than n/2 times, it is impossible to split the array into two groups of n/2 distinct elements each, because that number would have to appear in both groups, violating the distinctness requirement.

Approach

  1. Count the frequency of each number in the array.
  2. If the maximum frequency of any number is greater than n/2, return false.
  3. Otherwise, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    bool isPossibleToSplit(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;
        int n = nums.size() / 2;
        for (auto& [k, v] : freq) if (v > n) return false;
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func isPossibleToSplit(nums []int) bool {
    freq := make(map[int]int)
    for _, x := range nums {
        freq[x]++
    }
    n := len(nums) / 2
    for _, v := range freq {
        if v > n {
            return false
        }
    }
    return true
}
1
2
3
4
5
6
7
8
9

class Solution {
    public boolean isPossibleToSplit(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        int n = nums.length / 2;
        for (int v : freq.values()) if (v > n) return false;
        return true;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun isPossibleToSplit(nums: IntArray): Boolean {
        val freq = mutableMapOf<Int, Int>()
        for (x in nums) freq[x] = freq.getOrDefault(x, 0) + 1
        val n = nums.size / 2
        for (v in freq.values) if (v > n) return false
        return true
    }
}
1
2
3
4
5

def isPossibleToSplit(nums: list[int]) -> bool:
    from collections import Counter
    freq = Counter(nums)
    n = len(nums) // 2
    return all(v <= n for v in freq.values())
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

use std::collections::HashMap;
impl Solution {
    pub fn is_possible_to_split(nums: Vec<i32>) -> bool {
        let mut freq = HashMap::new();
        for x in nums.iter() {
            *freq.entry(*x).or_insert(0) += 1;
        }
        let n = nums.len() / 2;
        freq.values().all(|&v| v <= n)
    }
}
1
2
3
4
5
6
7
8

class Solution {
    isPossibleToSplit(nums: number[]): boolean {
        const freq: Record<number, number> = {};
        for (const x of nums) freq[x] = (freq[x] ?? 0) + 1;
        const n = nums.length / 2;
        return Object.values(freq).every(v => v <= n);
    }
}

Complexity

  • ⏰ Time complexity: O(n) – One pass to count, one pass to check frequencies.
  • 🧺 Space complexity: O(n) – Hash map for frequencies.