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.nums1 should contain distinct elements.nums2 should 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 == 0 1 <= nums[i] <= 100Problem 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.
The Breadth-First Search (BFS) approach involves exploring the neighbors of a node prior to moving on to the next level neighbors. This technique is typically implemented using a queue data structure to keep track of nodes being visited. BFS is particularly useful for finding the shortest path on unweighted graphs or levels of nodes.
Consider applying this approach when the question involves discovering nodes or levels layer by layer.
This C implementation uses a queue to perform a Breadth-First Search on a graph represented as an adjacency matrix. The BFS function keeps track of visited nodes to prevent cycles.
The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. The space complexity is O(V) due to the queue and visited list.
The Depth-First Search (DFS) approach explores as far along a branch as possible before backtracking. It is typically implemented using a stack, either explicitly or through recursion which utilizes the call stack. DFS is effective for path-finding and solving puzzles like mazes.
Consider using this approach when the problem can benefit from going deep into a particular path before considering alternatives.
This C implementation of DFS uses recursion to navigate the graph depth-first. It marks nodes as visited using an array and prints each visited node.
The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. Space complexity is O(V) for the visited array and can also be O(V) due to the recursive stack.
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.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. The space complexity is O(V) due to the queue and visited list. |
| Depth-First Search (DFS) Approach | The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. Space complexity is O(V) for the visited array and can also be O(V) due to the recursive stack. |
| Counting | — |
| 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 |
3046. Split the Array - LeetCode Weekly Contest 386 | Python, JavaScript, Java, C++ • CodingNinja • 1,056 views views
Watch 8 more video solutions →Practice Split the Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor