3046. Split the Array - LeetCode Weekly Contest 386 | Python, JavaScript, Java, C++
Split the Array - Video Solution
Watch 10 video solutions for Split the Array, a easy level problem involving Array, Hash Table, Counting. This walkthrough by CodingNinja has 1,103 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
Approach Overview
Problem Overview: You receive an integer array nums. The task is to determine whether it can be split into two arrays such that each resulting array contains only unique elements. An element may appear in both arrays, but duplicates inside the same array are not allowed.
Approach 1: Depth-First Search (Backtracking) (Time: O(2^n), Space: O(n))
Model the problem as assigning each number to one of two arrays. During recursion, try placing the current element into either array while ensuring no duplicate exists in that array. Use two sets to track elements already placed. If both placements violate the uniqueness rule, backtrack. This approach demonstrates the constraints clearly but becomes exponential because every element has two placement choices.
Approach 2: Breadth-First Search State Exploration (Time: O(2^n), Space: O(2^n))
Treat each partial assignment as a state in a queue. A state stores the current index and the elements placed in each array. For every number, generate new states by adding it to array A or B when the uniqueness constraint holds. BFS guarantees you explore all valid configurations level by level. This method is conceptually useful for understanding the assignment process but is impractical for large inputs due to the exponential state space.
Approach 3: Hash Counting (Optimal) (Time: O(n), Space: O(n))
The key observation: since there are only two arrays, any number can appear at most twice in the original array. If a value appears three or more times, at least one resulting array must contain a duplicate. Iterate through nums, maintain a frequency map using a hash table, and immediately return false if any count exceeds two. This turns the problem into a simple frequency validation using concepts from array traversal and counting.
Recommended for interviews: The hash counting approach is what interviewers expect. It reduces the problem to a simple invariant: each value can appear at most twice. Showing a brute-force DFS assignment first demonstrates reasoning about constraints, but recognizing the counting shortcut shows strong pattern recognition and leads to the optimal O(n) solution.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (Backtracking) | O(2^n) | O(n) | When exploring all possible assignments or explaining the constraint logically |
| Breadth-First Search (State Exploration) | O(2^n) | O(2^n) | Useful for conceptual state modeling or teaching assignment problems |
| Hash Counting (Optimal) | O(n) | O(n) | Best for interviews and production; quickly validates the frequency constraint |