Split the Array — Solution in Python, Java & C++
Split the Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and hash table.
Split the Array is an easy coding problem on arrays, hash table and counting, asked in Amazon, Google and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Counting
- Asked at: Amazon, Google, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 100nums.length % 2 == 01 <= nums[i] <= 100
Hints for Split the Array
Hint 1
Each half may hold a given value at most once.
Hint 2
So across both halves a value may appear at most twice.
Hint 3
Count the occurrences and check none exceeds 2.
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
- Count how often each value appears.
- Return
falsethe moment a count reaches 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())Java
public static boolean isPossibleToSplit(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
for (int v : nums) {
int c = count.merge(v, 1, Integer::sum);
if (c > 2) return false;
}
return true;
}C++
bool isPossibleToSplit(vector<int>& nums) {
unordered_map<int, int> count;
for (int v : nums) {
if (++count[v] > 2) return false;
}
return true;
}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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets