#3046

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Split the Array

Determine if an even-length array can be split into two parts with all distinct elements using hash lookup scanning.

Problem Statement

You are given an integer array nums with even length. You need to determine if it is possible to split nums into two arrays nums1 and nums2 where each array contains only distinct elements and together they include all original numbers.

Return true if such a split is possible and false if any number appears more than twice or prevents forming two distinct sets. Example: nums = [1,1,2,2,3,4] can be split into nums1 = [1,2,3] and nums2 = [1,2,4], but nums = [1,1,1,1] cannot be split to satisfy distinct requirements.

Examples

Example 1

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

Output: true

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

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 Approach

Count Occurrences

Scan nums and store the frequency of each number in a hash map. Immediately return false if any number occurs more than twice, as the pattern of array scanning plus hash lookup directly reveals impossible splits.

Distribute Numbers

Iterate through the frequency map and assign one occurrence of each number to nums1 and another to nums2 if a duplicate exists. This ensures both arrays have unique elements while maintaining total coverage.

Validate Split

Check the length and distinctness of nums1 and nums2 after assignment. Return true if both arrays have the expected number of elements and all elements are unique, confirming a successful split following the hash-based counting pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) to scan and count all numbers, plus O(n) to assign duplicates, giving overall O(n). Space complexity is O(n) for the hash map storing counts.

What Interviewers Usually Probe

Expecting hash map or frequency array to track occurrences.
Checking if any number occurs more than twice hints at early termination.
Distribution of duplicates across two arrays shows understanding of distinct set formation.

Common Pitfalls or Variants

Common pitfalls

Failing to immediately reject arrays with a number occurring more than twice.
Assuming any even-length array can be split without checking frequencies.
Overcomplicating the distribution instead of assigning one duplicate to each array.

Follow-up variants

Split array into k parts with distinct elements instead of just two.
Return one possible valid split instead of just true or false.
Handle arrays with negative numbers or larger ranges requiring generalized hash counting.

FAQ

What pattern is used to solve Split the Array efficiently?

The main pattern is array scanning plus hash lookup to count occurrences and identify impossible splits quickly.

Can I split an array if a number appears three times?

No, any number appearing more than twice prevents forming two arrays with distinct elements, so the answer is false.

How do I assign duplicates when splitting?

Place one occurrence in nums1 and one in nums2 to maintain distinct elements in both arrays.

What is the time complexity for this problem?

Time complexity is O(n) due to scanning the array and counting frequencies, with n being nums.length.

Does the solution work for arrays with even length only?

Yes, the problem constraint requires even-length arrays to allow splitting into two equal parts.

terminal

Solution

Solution 1: Counting

According to the problem, we need to divide the array into two parts, and the elements in each part are all distinct. Therefore, we can count the occurrence of each element in the array. If an element appears three or more times, it cannot satisfy the problem's requirements. Otherwise, we can divide the array into two parts.

1

2

3

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        return max(Counter(nums).values()) < 3

Continue Practicing

#3044 most frequent prime #3039 apply operations to make string empty #3035 maximum palindromes after operations