Skip to main content
Talentd

Split the Array - Solution & Explanation

EasyArrayHash TableCounting17 min readAsked at: Meta, Visa, Adobe +1
Practice this problem

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.
  • 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 <= 100
  • nums.length % 2 == 0
  • 1 <= 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.

Approach 1: Breadth-First Search (BFS) Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Depth-First Search (DFS) Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Counting

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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

3046. Split the Array - LeetCode Weekly Contest 386 | Python, JavaScript, Java, C++ • CodingNinja • 1,103 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Split the Array easy or hard?
Split the Array is classified as an Easy problem. The key insight is recognizing that each value can appear at most twice since the array is split into two arrays with unique elements.
Split the Array Python/Java solution
In Python, use a dictionary or collections.Counter to track frequencies and verify no element appears more than twice. In Java, use a HashMap<Integer, Integer> or an integer frequency array if the value range is small.
How to solve Split the Array in O(n)?
Traverse the array and maintain a frequency map using a hash table. For each number, increment its count and check whether the count exceeds two. If any value appears more than twice, return false immediately; otherwise return true after processing the array.
What is the best approach for Split the Array?
The optimal approach uses a hash map to count the frequency of each number. Since the array must be split into two arrays with unique elements, any value appearing more than twice makes the split impossible. A single pass counting solution runs in O(n) time with O(n) space.
Is Split the Array asked at Google/Amazon/Meta?
Variants of frequency counting and duplicate constraints appear frequently in interviews at companies like Amazon, Google, and Meta. Problems that reduce to hash counting and constraint validation are common in early interview rounds.
What data structure is used in Split the Array?
A hash table (hash map) is the primary data structure. It stores the frequency of each value while iterating through the array, allowing constant-time updates and checks.
What is the time complexity of Split the Array?
The optimal hash counting solution runs in O(n) time because you iterate through the array once and update a frequency map. Space complexity is O(n) in the worst case when all elements are distinct.

Ready to solve this problem?

Practice Split the Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays