# Check if it is Possible to Split Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-it-is-possible-to-split-array)
Canonical: https://scaleengineer.com/dsa/problems/check-if-it-is-possible-to-split-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
You are given an array `nums` of length `n` and an integer `m`. You need to determine if it is possible to split the array into `n` arrays of size 1 by performing a series of steps.

An array is called **good** if:

* The length of the array is **one**, or
* The sum of the elements of the array is **greater than or equal** to `m`.

In each step, you can select an existing array (which may be the result of previous steps) with a length of **at least two** and split it into **two** arrays, if both resulting arrays are good.

Return true if you can split the given array into `n` arrays, otherwise return false.

**Example 1:**

**Input:** nums = \[2, 2, 1\], m = 4

**Output:** true

**Explanation:**

* Split `[2, 2, 1]` to `[2, 2]` and `[1]`. The array `[1]` has a length of one, and the array `[2, 2]` has the sum of its elements equal to `4 >= m`, so both are good arrays.
* Split `[2, 2]` to `[2]` and `[2]`. both arrays have the length of one, so both are good arrays.

**Example 2:**

**Input:** nums = \[2, 1, 3\], m = 5

**Output:** false

**Explanation:**

The first move has to be either of the following:

* Split `[2, 1, 3]` to `[2, 1]` and `[3]`. The array `[2, 1]` has neither length of one nor sum of elements greater than or equal to `m`.
* Split `[2, 1, 3]` to `[2]` and `[1, 3]`. The array `[1, 3]` has neither length of one nor sum of elements greater than or equal to `m`.

So as both moves are invalid (they do not divide the array into two good arrays), we are unable to split `nums` into `n` arrays of size 1.

**Example 3:**

**Input:** nums = \[2, 3, 3, 2, 3\], m = 6

**Output:** true

**Explanation:**

* Split `[2, 3, 3, 2, 3]` to `[2]` and `[3, 3, 2, 3]`.
* Split `[3, 3, 2, 3]` to `[3, 3, 2]` and `[3]`.
* Split `[3, 3, 2]` to `[3, 3]` and `[2]`.
* Split `[3, 3]` to `[3]` and `[3]`.

**Constraints:**

* `1 <= n == nums.length <= 100`
* `1 <= nums[i] <= 100`
* `1 <= m <= 200`

# Approaches
## Dynamic Programming
A standard approach for problems involving optimal substructure and overlapping subproblems is dynamic programming. We can define a function `canSplit(i, j)` that returns true if the subarray `nums[i...j]` can be split into `j-i+1` arrays of size one. The result for `canSplit(i, j)` depends on the results of smaller subarrays, leading to a DP formulation.
**Time:** O(n^3) - We have three nested loops. The outer two loops iterate over all possible subarrays `(i, j)`, which is `O(n^2)`. The inner loop iterates over all possible split points `k`, which takes `O(n)` time. Calculating sums takes `O(1)` with the prefix sum array. · **Space:** O(n^2) - We use a 2D DP table of size n x n and a prefix sum array of size n+1.
**Pros:** It is a systematic approach that correctly solves the problem for the given constraints.; The logic is a direct translation of the problem's recursive definition, making it easier to verify correctness.
**Cons:** The `O(n^3)` time complexity might be too slow if the constraints on `n` were larger.; Requires `O(n^2)` space, which can be significant for larger `n`.
### Explanation
We can use a 2D DP table, `dp[i][j]`, to store whether the subarray `nums[i...j]` is splittable. We can build this table bottom-up, starting from smaller subarrays and building up to the entire array.

- **State:** `dp[i][j]` = `true` if `nums[i...j]` can be split, `false` otherwise.
- **Base Case:** For any subarray of length 1, `dp[i][i] = true`.
- **Transition:** To compute `dp[i][j]`, we iterate through all possible split points `k` from `i` to `j-1`. A split at `k` is possible if:
  1. The split itself is valid: The left part `nums[i...k]` is "good" AND the right part `nums[k+1...j]` is "good". An array is good if its length is 1 or its sum is `>= m`.
  2. The resulting subarrays can be fully split: `dp[i][k]` is `true` AND `dp[k+1][j]` is `true`.

If we find any such `k`, then `dp[i][j]` becomes `true`. To avoid recomputing subarray sums repeatedly, we can use a prefix sum array.

```java
class Solution {
    public boolean canSplitArray(List<Integer> nums, int m) {
        int n = nums.size();
        if (n <= 2) {
            return true;
        }

        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums.get(i);
        }

        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int k = i; k < j; k++) {
                    // Split into [i...k] and [k+1...j]
                    long leftSum = prefixSum[k + 1] - prefixSum[i];
                    boolean isLeftGood = (k - i + 1 == 1) || (leftSum >= m);

                    long rightSum = prefixSum[j + 1] - prefixSum[k + 1];
                    boolean isRightGood = (j - k == 1) || (rightSum >= m);

                    if (isLeftGood && isRightGood) {
                        if (dp[i][k] && dp[k+1][j]) {
                            dp[i][j] = true;
                            break;
                        }
                    }
                }
            }
        }

        return dp[0][n - 1];
    }
}
```
### Algorithm
- Create a 2D boolean array `dp[n][n]`, where `dp[i][j]` will store `true` if the subarray `nums[i...j]` can be fully split, and `false` otherwise.
- To handle subarray sum calculations efficiently, precompute a `prefixSum` array.
- The base cases for the DP are subarrays of length 1. `dp[i][i]` is `true` for all `i` from 0 to `n-1`, as a single-element array is already considered split.
- Iterate through all possible subarray lengths, from `len = 2` to `n`.
- For each length, iterate through all possible starting indices `i`.
- For each subarray `nums[i...j]` (where `j = i + len - 1`), try every possible split point `k` from `i` to `j-1`.
- A split at `k` divides `nums[i...j]` into `nums[i...k]` and `nums[k+1...j]`.
- This split is valid if both resulting subarrays are "good". A subarray is good if its length is 1 or its sum is greater than or equal to `m`.
- If the split is valid, we then check if the subarrays themselves can be further split by looking up our DP table: `dp[i][k]` and `dp[k+1][j]`.
- If we find any `k` for which the split is valid and both subproblems are solvable, we set `dp[i][j] = true` and break the inner loop (since we've found one way to split `nums[i...j]`)
- The final answer is the value of `dp[0][n-1]`.

## Greedy Approach with Key Observation
A more efficient solution can be derived from a key observation about the splitting process. For an array of length greater than 2, the possibility of splitting it down to single elements hinges on the ability to form 'good' subarrays of sum `>= m`. This can be simplified to a local condition involving adjacent elements.
**Time:** O(n) - We perform a single pass through the array to check for the condition on adjacent elements. · **Space:** O(1) - We only use a few variables for the loop and indices, requiring constant extra space.
**Pros:** Extremely efficient with linear time complexity.; Very simple to implement and requires constant extra space.; It is the most optimal solution.
**Cons:** The correctness of the approach relies on a non-trivial insight which might not be immediately obvious.
### Explanation
This approach simplifies the problem by identifying a necessary and sufficient condition for an array to be splittable.

**Base Cases:**
- If `n = 1`, the array is already split. `true`.
- If `n = 2`, we can split `[a, b]` into `[a]` and `[b]`. Both are good (length 1), so the split is valid. `true`.

**Core Insight (for n > 2):**
If there exists at least one pair of adjacent elements `nums[i]` and `nums[i+1]` such that their sum is `>= m`, we can guarantee a full split is possible. Here's why:
1. We can think of the split process in reverse: merging elements. We start with `n` individual elements.
2. If `nums[i] + nums[i+1] >= m`, we can merge them to form a block `B`. The reverse operation, splitting `B` into `[nums[i]]` and `[nums[i+1]]`, is valid because both `[nums[i]]` and `[nums[i+1]]` are good (length 1), and the array they form, `[nums[i], nums[i+1]]`, is also good because its sum is `>= m`.
3. Now we have `n-1` items, including the block `B`. We can merge `B` with an adjacent element, say `nums[i-1]`. The new block `B'` has `sum = sum(B) + nums[i-1] >= m + nums[i-1]`, which is also `>= m`. So, `B'` is a good block.
4. This process can be continued, merging the growing 'good' block with all other elements one by one. Each merge corresponds to a valid split in reverse.

Therefore, for `n > 2`, we only need to check for the existence of one such adjacent pair.

```java
class Solution {
    public boolean canSplitArray(List<Integer> nums, int m) {
        int n = nums.size();
        if (n <= 2) {
            return true;
        }
        
        for (int i = 0; i < n - 1; i++) {
            if (nums.get(i) + nums.get(i+1) >= m) {
                return true;
            }
        }
        
        return false;
    }
}
```
### Algorithm
- First, handle the edge cases. If the array length `n` is 1 or 2, it's always possible to split, so return `true`.
- If `n > 2`, the key insight is that the array can be fully split if and only if there exists at least one pair of adjacent elements whose sum is greater than or equal to `m`.
- Iterate through the array from `i = 0` to `n-2`.
- In each iteration, check if `nums[i] + nums[i+1] >= m`.
- If this condition is met for any `i`, it means we found a valid starting point for a sequence of splits, so we can immediately return `true`.
- If the loop completes without finding such a pair, it's impossible to perform the necessary splits, so return `false`.

# Solutions
### Java

```java
class Solution {
private
  Boolean[][] f;
private
  int[] s;
private
  int m;
public
  boolean canSplitArray(List<Integer> nums, int m) {
    int n = nums.size();
    f = new Boolean[n][n];
    s = new int[n + 1];
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + nums.get(i - 1);
    }
    this.m = m;
    return dfs(0, n - 1);
  }
private
  boolean dfs(int i, int j) {
    if (i == j) {
      return true;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    for (int k = i; k < j; ++k) {
      boolean a = k == i || s[k + 1] - s[i] >= m;
      boolean b = k == j - 1 || s[j + 1] - s[k + 1] >= m;
      if (a && b && dfs(i, k) && dfs(k + 1, j)) {
        return f[i][j] = true;
      }
    }
    return f[i][j] = false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canSplitArray(vector<int> &nums, int m) {
    int n = nums.size();
    vector<int> s(n + 1);
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + nums[i - 1];
    }
    int f[n][n];
    memset(f, -1, sizeof f);
    function<bool(int, int)> dfs = [&](int i, int j) {
      if (i == j) {
        return true;
      }
      if (f[i][j] != -1) {
        return f[i][j] == 1;
      }
      for (int k = i; k < j; ++k) {
        bool a = k == i || s[k + 1] - s[i] >= m;
        bool b = k == j - 1 || s[j + 1] - s[k + 1] >= m;
        if (a && b && dfs(i, k) && dfs(k + 1, j)) {
          f[i][j] = 1;
          return true;
        }
      }
      f[i][j] = 0;
      return false;
    };
    return dfs(0, n - 1);
  }
};

```

### Python

```python
class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool: @ cache def dfs(i: int, j: int) -> bool: if i == j: return True for k in range(i, j): a = k == i or s[k + 1] - s[i] >= m b = k == j - 1 or s[j + 1] - s[k + 1] >= m if a and b and dfs(i, k) and dfs(k + 1, j): return True return False s = list(accumulate(nums, initial=0)) return dfs(0, len(nums) - 1)

```