Split the Array
EasyPrompt
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.nums1should contain distinct elements.nums2should also contain distinct elements.
Return true if it is possible to split the array, and false otherwise.
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 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 <= 100nums.length % 2 == 01 <= nums[i] <= 100
Approaches
4 approaches with complexity analysis and trade-offs.
A more efficient approach is based on the key insight that a valid split is impossible if and only if some number appears more than twice. By sorting the array, we can easily check this condition. If any number appears three or more times, these identical elements will be grouped together after sorting.
Algorithm
- Sort the input array
numsin non-decreasing order. - Iterate through the array from index
i = 0ton-3, wherenis the length of the array. - In each iteration, check if
nums[i]is equal tonums[i+2]. - If they are equal, it means the number
nums[i]appears at least three times, so returnfalse. - If the loop completes without finding any such triplet, return
true.
Walkthrough
The core idea is that if a number x appears 3 or more times, we cannot place all instances of x into nums1 and nums2 without one of them having duplicate x's. For example, with three x's, by the pigeonhole principle, at least one array must get two x's, violating the distinctness rule. Conversely, if every number appears at most twice, a valid split is always possible.
The algorithm first sorts the input array nums. This brings all identical elements next to each other.
Then, it iterates through the sorted array and checks for any element that is repeated three or more times. A simple way to do this is to check if nums[i] == nums[i+2] for any i. If this condition is met, it implies nums[i], nums[i+1], and nums[i+2] are all the same, so we can immediately return false.
If the entire array is scanned without finding such a triplet, it means no number appears more than twice, and we can return true.
import java.util.Arrays; class Solution { public boolean isPossibleToSplit(int[] nums) { int n = nums.length; if (n < 2) { return true; } Arrays.sort(nums); for (int i = 0; i < n - 2; i++) { if (nums[i] == nums[i+2]) { // This means nums[i], nums[i+1], and nums[i+2] are all equal return false; } } return true; }}Complexity
Time
O(n log n), dominated by the sorting step. The subsequent scan is `O(n)`.
Space
O(log n) or O(n), depending on the space used by the sorting algorithm implementation (e.g., quicksort's recursion stack or mergesort's auxiliary array).
Trade-offs
Pros
Much more efficient than backtracking.
Simple to implement.
Cons
The
O(n log n)time complexity from sorting is not the most optimal.
Solutions
Solution
public class Solution { public bool IsPossibleToSplit(int[] nums) { int[] cnt = new int[101]; foreach(int x in nums) { if (++cnt[x] >= 3) { return false; } } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.