# Split the Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/split-the-array)
Canonical: https://scaleengineer.com/dsa/problems/split-the-array
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Visa](https://scaleengineer.com/companies/visa)
---
## Problem
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`

# Approaches
## Brute-force with Backtracking
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.
**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.
**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.
### Explanation
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:
1. Place `nums[index]` into `nums1`: This is possible only if `nums1` is not yet full (size < `n/2`) and does not already contain `nums[index]`. If we can place it, we make a recursive call for the next index, `index + 1`. If the recursive call returns `true`, we propagate `true` up. Otherwise, we backtrack by removing the element from `nums1`.
2. Place `nums[index]` into `nums2`: Similarly, we try to place the element in `nums2` if it's not full and doesn't contain `nums[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`.
```java
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;
    }
}
```
### Algorithm
- Create a recursive helper function `canSplitHelper(index, nums, set1, set2, halfSize)`.
- Base Case: If `index` equals `nums.length`, return `true`.
- Recursive Step:
  - Get the current number `nums[index]`.
  - Attempt to add `currentNum` to `set1` if it has space and `currentNum` is not present.
  - If successful, recursively call `canSplitHelper(index + 1, ...)` for the next element. If it returns `true`, propagate `true`.
  - If the recursive call fails, backtrack by removing `currentNum` from `set1`.
  - Attempt to add `currentNum` to `set2` if it has space and `currentNum` is not present.
  - If successful, recursively call `canSplitHelper(index + 1, ...)` for the next element. If it returns `true`, propagate `true`.
  - If the recursive call fails, backtrack by removing `currentNum` from `set2`.
- If neither placement leads to a solution, return `false`.

## Sorting and Checking for Duplicates
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.
**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).
**Pros:** Much more efficient than backtracking.; Simple to implement.
**Cons:** The `O(n log n)` time complexity from sorting is not the most optimal.
### Explanation
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`.
```java
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;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Iterate through the array from index `i = 0` to `n-3`, where `n` is the length of the array.
- In each iteration, check if `nums[i]` is equal to `nums[i+2]`.
- If they are equal, it means the number `nums[i]` appears at least three times, so return `false`.
- If the loop completes without finding any such triplet, return `true`.

## Frequency Counting with a HashMap
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.
**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)`.
**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).
### Explanation
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:
1. **Build Frequency Map**: Iterate through the `nums` array. For each number, update its count in a `HashMap<Integer, Integer>`.
2. **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.
```java
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;
    }
}
```
### Algorithm
- Initialize an empty `HashMap` to store number frequencies.
- Iterate through each `num` in the input array `nums`.
- For each `num`, increment its count in the `HashMap`.
- After incrementing, check if the new count for `num` is greater than 2.
- If it is, return `false` immediately.
- If the loop completes without any count exceeding 2, return `true`.

## Frequency Counting with an Array
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.
**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`.
**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.
### Explanation
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:
1. Initialize an integer array `counts` of size 101 to all zeros.
2. Iterate through the input array `nums`. For each `num`, increment `counts[num]`.
3. 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 return `false` immediately.

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.
```java
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;
    }
}
```
### Algorithm
- Create an integer array `counts` of size 101 and initialize all its elements to 0.
- Iterate through each number `num` in the input array `nums`.
- For each `num`, use it as an index to increment the count in the `counts` array: `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`.

# Solutions
### CSharp

```csharp
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;
    }
}
```

### Java

```java
class Solution {
public
  boolean isPossibleToSplit(int[] nums) {
    int[] cnt = new int[101];
    for (int x : nums) {
      if (++cnt[x] >= 3) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isPossibleToSplit(vector<int> &nums) {
    int cnt[101]{};
    for (int x : nums) {
      if (++cnt[x] >= 3) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def isPossibleToSplit(
        self, nums: List[int]) -> bool: return max(Counter(nums). values()) < 3

```