LeetCode 3046 - Split the Array

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to determine if an even-length array can be split into two equal-sized subarrays, each containing only distinct elements. In other words, we must partition the array nums of length n into nums1 and nums2 of size n/2 such that there are no repeated numbers within either subarray. The function should return true if such a partition exists, and false otherwise.

The key points to note are:

nums has an even length, so splitting it into two equal parts is always possible in terms of size.
Each subarray must have all unique elements; duplicates across the split are allowed.
The maximum possible length of nums is 100, and values are small integers (1 to 100), so solutions with O(n) or O(n log n) complexity are acceptable.
The main constraint is the number of unique elements: if there are too few distinct numbers, some duplicates will necessarily end up in the same half, violating the distinct requirement.

Edge cases that may trip a naive implementation include arrays where all elements are identical or arrays where there are exactly n/2 unique elements.

Approaches

A brute-force approach would attempt to generate all possible splits of the array into two equal halves and check whether both halves contain only distinct elements. While this is correct, it is exponentially expensive because the number of combinations grows rapidly as n increases (specifically, O(choose(n, n/2))).

The optimal approach relies on the insight that the number of unique elements determines whether a valid split exists. Let unique_count be the number of distinct integers in the array. For a valid split:

Each half must contain exactly n/2 elements.
No half can contain duplicates, so each half can contain at most unique_count unique numbers.
The minimum number of unique numbers required in the array is at least n/2. If unique_count is smaller than n/2, some duplicates will inevitably be forced into the same half, making the split impossible.

Thus, the solution is to count the number of distinct elements and check if it is greater than or equal to n/2.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(choose(n, n/2) * n)	O(n)	Generate all splits and check distinctness
Optimal	O(n)	O(n)	Count unique elements using a set, then compare with n/2

Algorithm Walkthrough

Determine the length of the array, n.
Create a set or hash map to count the number of distinct elements in nums.
Compute the number of unique elements in the array and store it as unique_count.
Compare unique_count to n/2. If unique_count >= n/2, return true; otherwise, return false.

Why it works: The key invariant is that each subarray can have at most n/2 elements, so at least n/2 distinct elements are required to avoid duplicates in either subarray. If the array has fewer than n/2 unique elements, some duplicates will necessarily be forced into the same half, making a valid split impossible.

Python Solution

from typing import List

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        n = len(nums)
        unique_count = len(set(nums))
        return unique_count >= n // 2

The Python implementation first converts the input list into a set, which automatically removes duplicates. Then it calculates the length of this set to determine how many unique elements exist. Finally, it compares this count with n/2 to decide if a valid split is possible.

Go Solution

func isPossibleToSplit(nums []int) bool {
    uniqueMap := make(map[int]bool)
    for _, num := range nums {
        uniqueMap[num] = true
    }
    return len(uniqueMap) >= len(nums)/2
}

In Go, a map is used to track distinct elements. The key is the number itself, and the value is a dummy boolean. After populating the map, the number of unique elements is len(uniqueMap), which is then compared to half of the array length.

Go-specific notes: unlike Python, Go requires explicit map creation, and len(map) gives the number of keys. This approach avoids using slices or arrays for counting and works efficiently for small integers.

Worked Examples

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

Step	Operation	Result
1	Create set from nums	{1,2,3,4}
2	Count unique elements	4
3	Compare with n/2 (6/2=3)	4 >= 3 → true

Example 2: nums = [1,1,1,1]

Step	Operation	Result
1	Create set from nums	{1}
2	Count unique elements	1
3	Compare with n/2 (4/2=2)	1 < 2 → false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Iterating through the array to build a set or map takes linear time
Space	O(n)	The set/map stores up to n unique elements

The complexity is optimal given the constraints. Even in the worst case where all elements are distinct, we only require linear time and space.

Test Cases

# Provided examples
assert Solution().isPossibleToSplit([1,1,2,2,3,4]) == True  # standard case with enough distinct numbers
assert Solution().isPossibleToSplit([1,1,1,1]) == False     # all elements identical, impossible

# Boundary cases
assert Solution().isPossibleToSplit([1,2]) == True           # minimal valid split, 2 elements, 2 unique
assert Solution().isPossibleToSplit([1,1]) == False          # minimal invalid split, 2 elements, 1 unique

# Stress cases
assert Solution().isPossibleToSplit(list(range(1, 101)) * 1) == True  # 100 elements, all distinct
assert Solution().isPossibleToSplit([1]*50 + [2]*50) == True          # exactly 2 unique elements, each duplicated, n/2 = 50
assert Solution().isPossibleToSplit([1]*99 + [2]) == False             # 100 elements, only 2 unique, n/2 = 50 → false

Test	Why
[1,1,2,2,3,4]	Enough distinct numbers for split
[1,1,1,1]	Not enough distinct numbers
[1,2]	Minimal valid case
[1,1]	Minimal invalid case
range(1,101)	Maximum size array with all distinct
[1]50 + [2]50	Duplicates but still possible
[1]*99 + [2]	Edge case with insufficient distinct numbers

Edge Cases

All identical elements: Arrays like [1,1,1,1] will always return false because there is only one unique element, which is insufficient to fill both halves.

Minimal even-length arrays: Arrays of length 2 need exactly 2 unique elements to return true. [1,2] is valid, [1,1] is invalid.

Arrays with exactly n/2 unique elements: In this scenario, each half can contain all the unique elements without duplicates, so the algorithm correctly returns true. For example, [1,2,3,1,2,3] with length 6 has 3 unique elements, equal to n/2, so a valid split exists.