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.
This approach directly implements the core logic by counting the occurrences of each number. It uses a HashMap to store the frequency of each element in the nums array. If any number's frequency exceeds 2, a valid split is impossible.
Algorithm
- Initialize an empty
HashMapto store number frequencies. - Iterate through each
numin the input arraynums. - For each
num, increment its count in theHashMap. - After incrementing, check if the new count for
numis greater than 2. - If it is, return
falseimmediately. - If the loop completes without any count exceeding 2, return
true.
Walkthrough
The logic remains the same: a split is possible if and only if no number appears more than twice. We can determine the frequency of each number efficiently using a hash map.
The algorithm involves two main steps:
- Build Frequency Map: Iterate through the
numsarray. For each number, update its count in aHashMap<Integer, Integer>. - Check Frequencies: Iterate through the values (the counts) of the hash map. If any count is greater than 2, return
false.
If we finish checking all counts without finding one greater than 2, it means a valid split is possible, so we return true. This approach avoids sorting and achieves a linear time complexity. An optimization is to check the count immediately after updating it, which can lead to an early exit.
import java.util.HashMap;import java.util.Map; class Solution { public boolean isPossibleToSplit(int[] nums) { Map<Integer, Integer> frequencyMap = new HashMap<>(); for (int num : nums) { int newCount = frequencyMap.getOrDefault(num, 0) + 1; if (newCount > 2) { return false; } frequencyMap.put(num, newCount); } return true; }}Complexity
Time
O(n), as we iterate through the array once to build the map and check frequencies.
Space
O(U), where `U` is the number of unique elements in `nums`. In the worst case, `U` can be `n`, so the space complexity is `O(n)`.
Trade-offs
Pros
Achieves linear time complexity, which is better than the sorting approach.
Works for any range of input numbers.
Cons
Uses extra space for the HashMap, which can be up to
O(n)in the worst case (all elements are distinct).
This is the most optimal approach, leveraging the problem's constraint that the numbers in the array are within a small, fixed range (1 <= nums[i] <= 100). Instead of a HashMap, we can use a simple array as a frequency counter, which is faster and uses constant space.
Algorithm
- Create an integer array
countsof size 101 and initialize all its elements to 0. - Iterate through each number
numin the input arraynums. - For each
num, use it as an index to increment the count in thecountsarray:counts[num]++. - After incrementing, check if
counts[num]is now greater than 2. - If it is, return
false. - If the loop completes, it means no number appeared more than twice. Return
true.
Walkthrough
Given that the values of nums[i] are between 1 and 100, we can use an integer array, say counts, of size 101 to store the frequency of each number. The index of the array corresponds to the number, and the value at that index is its frequency.
The algorithm is very simple:
- Initialize an integer array
countsof size 101 to all zeros. - Iterate through the input array
nums. For eachnum, incrementcounts[num]. - As soon as we increment a count, we check if it has become greater than 2. If
counts[num] > 2, we know a split is impossible and can returnfalseimmediately.
If the loop finishes without any frequency exceeding 2, it means a valid split is possible, and we return true. This method is highly efficient due to direct array indexing instead of hash computations and has a constant space footprint.
class Solution { public boolean isPossibleToSplit(int[] nums) { int[] counts = new int[101]; // For numbers 1 to 100 for (int num : nums) { counts[num]++; if (counts[num] > 2) { return false; } } return true; }}Complexity
Time
O(n), as we iterate through the input array once.
Space
O(1), as the size of the `counts` array (101) is constant and does not depend on the size of the input array `n`.
Trade-offs
Pros
The most efficient solution in both time and space.
It has linear time complexity and constant space complexity.
Cons
This approach is only applicable because the range of input values is small and known beforehand. It would not be suitable if the numbers could be very large or unbounded.
This approach explores all possible ways to partition the array nums into two sub-arrays, nums1 and nums2, each of size n/2. It uses a recursive backtracking algorithm to try placing each element of nums into either nums1 or nums2, ensuring that the distinctness and size constraints are met at each step.
Algorithm
- Create a recursive helper function
canSplitHelper(index, nums, set1, set2, halfSize). - Base Case: If
indexequalsnums.length, returntrue. - Recursive Step:
- Get the current number
nums[index]. - Attempt to add
currentNumtoset1if it has space andcurrentNumis not present. - If successful, recursively call
canSplitHelper(index + 1, ...)for the next element. If it returnstrue, propagatetrue. - If the recursive call fails, backtrack by removing
currentNumfromset1. - Attempt to add
currentNumtoset2if it has space andcurrentNumis not present. - If successful, recursively call
canSplitHelper(index + 1, ...)for the next element. If it returnstrue, propagatetrue. - If the recursive call fails, backtrack by removing
currentNumfromset2.
- Get the current number
- If neither placement leads to a solution, return
false.
Walkthrough
We define a recursive function, say canSplitHelper(index), which tries to place the element nums[index] and all subsequent elements. The state of the recursion includes the current index being considered and the two sets representing nums1 and nums2 being built.
The base case for the recursion is when index reaches the end of the array (nums.length). If we've successfully placed all elements, it means a valid split is found, and we return true.
In the recursive step for nums[index], we have two choices:
- Place
nums[index]intonums1: This is possible only ifnums1is not yet full (size <n/2) and does not already containnums[index]. If we can place it, we make a recursive call for the next index,index + 1. If the recursive call returnstrue, we propagatetrueup. Otherwise, we backtrack by removing the element fromnums1. - Place
nums[index]intonums2: Similarly, we try to place the element innums2if it's not full and doesn't containnums[index]. We make a recursive call and backtrack if necessary.
If neither choice leads to a solution, the function returns false. The initial call would be canSplitHelper(0) with empty sets for nums1 and nums2.
import java.util.HashSet;import java.util.Set; class Solution { public boolean isPossibleToSplit(int[] nums) { int n = nums.length; return canSplitHelper(0, nums, new HashSet<>(), new HashSet<>(), n / 2); } private boolean canSplitHelper(int index, int[] nums, Set<Integer> set1, Set<Integer> set2, int halfSize) { if (index == nums.length) { return true; } int currentNum = nums[index]; // Try placing in set1 if (set1.size() < halfSize && !set1.contains(currentNum)) { set1.add(currentNum); if (canSplitHelper(index + 1, nums, set1, set2, halfSize)) { return true; } set1.remove(currentNum); // Backtrack } // Try placing in set2 if (set2.size() < halfSize && !set2.contains(currentNum)) { set2.add(currentNum); if (canSplitHelper(index + 1, nums, set1, set2, halfSize)) { return true; } set2.remove(currentNum); // Backtrack } return false; }}Complexity
Time
O(2^n), where `n` is the length of `nums`. At each of the `n` steps, we explore up to two branches.
Space
O(n), for the recursion stack depth and to store the elements in the two sets.
Trade-offs
Pros
It's a conceptually straightforward way to explore the entire search space.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
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; }}class Solution {public boolean isPossibleToSplit(int[] nums) { int[] cnt = new int[101]; for (int x : nums) { if (++cnt[x] >= 3) { return false; } } return true; }}class Solution {public: bool isPossibleToSplit(vector<int> &nums) { int cnt[101]{}; for (int x : nums) { if (++cnt[x] >= 3) { return false; } } return true; }};class Solution: def isPossibleToSplit( self, nums: List[int]) -> bool: return max(Counter(nums). values()) < 3Video 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.