# Ways to Split Array Into Good Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/ways-to-split-array-into-good-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/ways-to-split-array-into-good-subarrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given a binary array `nums`.

A subarray of an array is **good** if it contains **exactly** **one** element with the value `1`.

Return _an integer denoting the number of ways to split the array_ `nums` _into **good** subarrays_. As the number may be too large, return it **modulo** `109 + 7`.

A subarray is a contiguous **non-empty** sequence of elements within an array.

**Example 1:**

**Input:** nums = [0,1,0,0,1]
**Output:** 3
**Explanation:** There are 3 ways to split nums into good subarrays:
- [0,1] [0,0,1]
- [0,1,0] [0,1]
- [0,1,0,0] [1]

**Example 2:**

**Input:** nums = [0,1,0]
**Output:** 1
**Explanation:** There is 1 way to split nums into good subarrays:
- [0,1,0]

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 1`

# Approaches
## Dynamic Programming (Naive)
This approach uses dynamic programming to solve the problem. We define `dp[i]` as the number of ways to split the prefix of the array `nums[0...i-1]` into good subarrays. To compute `dp[i]`, we look for all possible last good subarrays ending at `i-1`. If `nums[j...i-1]` is a good subarray, it contributes `dp[j]` ways to `dp[i]`. Summing these up for all valid `j` gives the value of `dp[i]`. The final answer is the value of `dp[n]`.
**Time:** O(N^2), due to the nested loops for computing the DP table. The outer loop runs N times and the inner loop runs up to N times. · **Space:** O(N), for the DP array `dp` and the `prefixOnes` array.
**Pros:** It's a systematic way to solve the problem that builds the solution from smaller subproblems.; Guaranteed to find the correct answer if it runs within the time limit.
**Cons:** The O(N^2) time complexity is inefficient and will likely result in a 'Time Limit Exceeded' error for the given constraints (N up to 10^5).; Requires O(N) extra space for the DP table and the prefix sums array.
### Explanation
The state `dp[i]` represents the number of ways to partition the subarray `nums[0...i-1]` into good subarrays. The final answer will be `dp[n]`. The base case is `dp[0] = 1`, representing one way to partition an empty array (the empty partition). The recurrence relation is `dp[i] = sum(dp[j])` for all `0 <= j < i` such that the subarray `nums[j...i-1]` is "good" (contains exactly one `1`). To efficiently check if `nums[j...i-1]` is good, we can precompute a prefix sum array `prefix_ones`, where `prefix_ones[k]` stores the count of `1`s in `nums[0...k-1]`. The number of `1`s in `nums[j...i-1]` is then `prefix_ones[i] - prefix_ones[j]`. The algorithm iterates `i` from 1 to `n`, and for each `i`, it iterates `j` from 0 to `i-1`, checking the condition and updating `dp[i]`. If the array contains no `1`s, this formulation correctly yields 0.

```java
class Solution {
    public int numberOfGoodSubarraySplits(int[] nums) {
        int n = nums.length;
        long MOD = 1_000_000_007;

        int[] prefixOnes = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixOnes[i + 1] = prefixOnes[i] + nums[i];
        }

        long[] dp = new long[n + 1];
        dp[0] = 1; // Base case: one way to split an empty prefix

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // Check if subarray nums[j...i-1] is good
                if (prefixOnes[i] - prefixOnes[j] == 1) {
                    dp[i] = (dp[i] + dp[j]) % MOD;
                }
            }
        }
        return (int) dp[n];
    }
}
```
### Algorithm
- Create a prefix sum array `prefix_ones` of size `n+1`, where `prefix_ones[i]` stores the count of `1`s in `nums[0...i-1]`.
- Create a DP array `dp` of size `n+1`, initialized to 0. Set `dp[0] = 1` to represent one way to partition an empty prefix (the empty partition).
- Iterate `i` from 1 to `n`:
  - Inside, iterate `j` from 0 to `i-1`:
    - If `prefix_ones[i] - prefix_ones[j] == 1`, it means the subarray `nums[j...i-1]` is a good subarray.
    - In this case, add `dp[j]` to `dp[i]`, as the number of ways to split `nums[0...i-1]` ending with the good subarray `nums[j...i-1]` is equal to the number of ways to split the prefix `nums[0...j-1]`.
- Remember to perform all additions modulo `10^9 + 7`.
- The final answer is `dp[n]`, which represents the total number of ways to split the entire array `nums[0...n-1]`.

## Two-Pass Approach using Index List
A more efficient approach comes from a combinatorial insight. A valid split of the array into good subarrays means each subarray contains exactly one `1`. This implies that the splits must occur in the spaces between the `1`s. The number of ways to place a split between two consecutive `1`s at indices `i` and `j` is simply the number of positions available, which is `j - i`. The total number of ways is the product of these counts for all consecutive pairs of `1`s.
**Time:** O(N), as we iterate through the array once to find the indices and then iterate through the list of indices once. The size of the index list is at most N. · **Space:** O(K), where K is the number of `1`s in the array. In the worst case, if all elements are `1`s, the space complexity is O(N).
**Pros:** Much more efficient than the naive DP, with O(N) time complexity.; The logic is intuitive and directly models the structure of the problem.
**Cons:** Requires O(K) extra space to store the indices of the `1`s, where K is the number of `1`s. In the worst case, K can be equal to N.
### Explanation
First, we handle the edge cases: if the array contains no `1`s, no split is possible, so the answer is 0. If it contains only one `1`, the only way is to take the whole array as a single good subarray, so the answer is 1. The core idea is to find the indices of all `1`s in the array. We iterate through the array once to collect all indices where `nums[i] == 1` into a list. Then, we iterate through this list of indices. For each pair of consecutive indices `idx_prev` and `idx_curr`, the number of ways to place a split between them is `idx_curr - idx_prev`. We multiply these counts together to get the total number of ways. Since the result can be large, we perform multiplication modulo `10^9 + 7`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int numberOfGoodSubarraySplits(int[] nums) {
        long MOD = 1_000_000_007;
        List<Integer> oneIndices = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                oneIndices.add(i);
            }
        }

        if (oneIndices.isEmpty()) {
            return 0;
        }

        long ways = 1;
        for (int i = 0; i < oneIndices.size() - 1; i++) {
            long gap = oneIndices.get(i + 1) - oneIndices.get(i);
            ways = (ways * gap) % MOD;
        }

        return (int) ways;
    }
}
```
### Algorithm
- Create a list to store the indices of all `1`s.
- Iterate through `nums` and populate this list.
- If the list of indices is empty, it means there are no `1`s, so return 0.
- If the list has only one element, it means there is only one `1`. The only way is to consider the whole array as one good subarray, so return 1.
- Initialize a variable `ways` to 1.
- Iterate through the list of indices from the first element up to the second-to-last element.
- In each iteration `i`, calculate the difference between the next index and the current index: `gap = indices.get(i+1) - indices.get(i)`.
- Multiply `ways` by `gap`, taking the result modulo `10^9 + 7`: `ways = (ways * gap) % MOD`.
- After the loop, return the final `ways`.

## Single-Pass Optimal Approach
This approach is an optimization of the two-pass method. Instead of storing all indices of `1`s in a list first, we can calculate the product of gaps on the fly in a single pass through the array. This eliminates the need for extra storage for the indices, reducing the space complexity to constant.
**Time:** O(N), as we iterate through the input array only once. · **Space:** O(1), as we only use a few variables to store the running product and the last seen index, regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Simple and elegant implementation.
**Cons:** There are no significant cons to this approach as it is optimal in both time and space.
### Explanation
We iterate through the array, keeping track of the index of the last `1` we encountered. When we find a `1`, if it's not the very first `1` we've seen, we calculate the distance between its current index and the index of the previous `1`. This distance represents the number of ways to place a split between these two `1`s. We multiply our running total by this distance. We need to handle the initial state carefully. We can use a variable, say `last_one_index`, initialized to -1. When we find the first `1`, we just record its index. For subsequent `1`s, we calculate the gap and update `last_one_index`. If after iterating through the whole array no `1` was found, the answer is 0. Otherwise, the accumulated product is the answer. If only one `1` is found, the product loop is never entered, and the initial value of 1 is correctly returned.

```java
class Solution {
    public int numberOfGoodSubarraySplits(int[] nums) {
        long MOD = 1_000_000_007;
        long ways = 1;
        int lastOneIndex = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                if (lastOneIndex != -1) {
                    long gap = i - lastOneIndex;
                    ways = (ways * gap) % MOD;
                }
                lastOneIndex = i;
            }
        }

        if (lastOneIndex == -1) {
            return 0; // No '1's found in the array
        }

        return (int) ways;
    }
}
```
### Algorithm
- Initialize `ways = 1`, `last_one_index = -1`, and `MOD = 10^9 + 7`.
- Iterate through the array `nums` with index `i`.
- If `nums[i] == 1`:
  - If `last_one_index` is not -1 (i.e., this is not the first `1` found):
    - Calculate the gap: `gap = i - last_one_index`.
    - Multiply `ways` by `gap`: `ways = (ways * gap) % MOD`.
  - Update `last_one_index = i`.
- After the loop, if `last_one_index` is still -1, it means there were no `1`s in the array. Return 0.
- Otherwise, return `ways`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int NumberOfGoodSubarraySplits(int[] nums) {
        long ans = 1, j = -1;
        int mod = 1000000007;
        int n = nums.Length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                continue;
            }
            if (j > -1) {
                ans = ans * (i - j) % mod;
            }
            j = i;
        }
        return j == -1 ? 0 : (int) ans;
    }
}
```

### Java

```java
class Solution {
public
  int numberOfGoodSubarraySplits(int[] nums) {
    final int mod = (int)1 e9 + 7;
    int ans = 1, j = -1;
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] == 0) {
        continue;
      }
      if (j > -1) {
        ans = (int)((long)ans * (i - j) % mod);
      }
      j = i;
    }
    return j == -1 ? 0 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfGoodSubarraySplits(vector<int> &nums) {
    const int mod = 1e9 + 7;
    int ans = 1, j = -1;
    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i] == 0) {
        continue;
      }
      if (j > -1) {
        ans = 1LL * ans * (i - j) % mod;
      }
      j = i;
    }
    return j == -1 ? 0 : ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfGoodSubarraySplits(self, nums: List[int]) -> int: mod = 10 ** 9 + 7 ans, j = 1, - 1 for i, x in enumerate(nums): if x == 0: continue if j > - 1: ans = ans * (i - j) % mod j = i return 0 if j == - 1 else ans

```