Split the Array — Easy Problem & Solution

Problem statement

nums has an even length. Split it into two arrays nums1 and nums2 of equal length so that each of them holds only distinct values.

Return true if such a split exists.

Example 1

Input: nums = [1,1,2,2,3,4]
Output: true
Explanation: `[1,2,3]` and `[1,2,4]`.

Example 2

Input: nums = [1,1,1,1]
Output: false
Explanation: The value 1 appears four times, so one half must repeat it.

Example 3

Input: nums = [5,5]
Output: true

Constraints

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

How to solve Split the Array

A split exists exactly when no value occurs more than twice, because the two halves can hold at most one copy each.

Approach

1. Count how often each value appears.
2. Return false the moment a count reaches 3.
3. Otherwise return true.

Why it works

The condition is not just necessary but sufficient: with every count at most 2, send one copy of each value to each half and the halves come out the same size, because the array's length is even and the leftovers pair up. So no construction is needed — counting decides it.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The limit is 2 across the whole array, not 2 per half.
• The length is guaranteed even, so the sizes never need checking.
• Sorting works too but is slower than counting.

Reference solution

Python

from typing import List
from collections import Counter

def isPossibleToSplit(nums: List[int]) -> bool:
    return all(c <= 2 for c in Counter(nums).values())

JavaScript

var isPossibleToSplit = function(nums) {
    var count = new Map();
    for (var i = 0; i < nums.length; i++) {
        var cur = count.get(nums[i]);
        var c = (cur === undefined ? 0 : cur) + 1;
        if (c > 2) return false;
        count.set(nums[i], c);
    }
    return true;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy