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 <= 1050 <= nums[i] <= 1Problem Overview: You are given a binary array and need to count how many ways it can be split into contiguous subarrays where each subarray contains exactly one 1. Zeros can appear anywhere inside a subarray, but every segment must include one and only one 1. The task reduces to counting valid split points between consecutive ones.
Approach 1: Gap Counting Method (O(n) time, O(1) space)
The key observation: every valid subarray must contain exactly one 1. That means splits can only occur between two consecutive 1 values. Count the number of zeros between each pair of ones. If there are k zeros between them, you have k + 1 possible places to split while still keeping one 1 per segment. Multiply these choices across all adjacent pairs of ones. Implementation is straightforward: iterate through the array, record the index of the previous 1, compute the gap when the next 1 appears, and multiply the answer by that gap size. If the array contains no 1, return 0 because forming a valid subarray is impossible. This solution uses simple arithmetic and a single pass, making it the most efficient approach for array problems involving binary structure.
Approach 2: Prefix Count Method (O(n) time, O(1) space)
This version frames the problem using running counts similar to lightweight dynamic programming. Track how many zeros appear after the previous 1. When a new 1 appears, those zeros represent multiple possible boundaries for the previous segment. Maintain a running number of valid splits and update it using multiplication with zeroCount + 1. Conceptually this treats each 1 as starting a new segment while the zeros between ones determine how many prefixes can form valid partitions. The logic is almost identical to the gap method but expressed through prefix tracking instead of explicit index gaps.
Both approaches rely on a simple combinatorial insight: the total number of valid splits equals the product of choices created by zeros between ones. The computation naturally fits problems combining math reasoning with linear array traversal.
Recommended for interviews: The Gap Counting Method is what interviewers typically expect. It shows you recognized the combinatorial structure of the array instead of brute‑forcing split positions. Explaining why each zero gap contributes gap + 1 choices demonstrates strong problem decomposition and leads directly to the optimal O(n) solution.
This approach involves counting the zero gaps between consecutive `1`s. Each zero gap can provide a multiplicative factor to the number of ways we can split the array around `1`s to form good subarrays. To solve this, iterate through the `nums` array, and whenever a `1` is found, calculate the number of splits using zero gaps encountered so far and multiply this with the previous result. Track the zeros between `1`s using a counter.
We initialize our main variables: `MOD` to handle modulo operation, `ways` to calculate the number of split ways, and `zero_count` to keep track of zeros between `1`s. As we iterate, each `1` encountered helps us accumulate the result by factoring in the preceding zeros. Finally, return `ways` if there is at least one `1` in the array.
Time Complexity: O(n) - since we only traverse the array once.
Space Complexity: O(1) - as we use a constant space to manage the counters.
This approach leverages the counting of cumulative prefixes which might split into valid subarrays. By considering the prefix sums at each point, we deliberately choose indices to count potential good subarrays, focusing shifts for every `1` encountered.
In this C# solution, we translate our understanding of prefixes into tracking how frequently zero sequences can combine betwixt `1`s. Similar methodology to other language solutions but adjusts for zero gaps per `1` encounter.
C#
JavaScript
Time Complexity: O(n) - single traversal executes over the array.
Space Complexity: O(1) - non-growing storage usage.
| Approach | Complexity |
|---|---|
| Gap Counting Method | Time Complexity: O(n) - since we only traverse the array once. |
| Prefix Count Method | Time Complexity: O(n) - single traversal executes over the array. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Gap Counting Method | O(n) | O(1) | Best general solution for binary arrays; minimal memory and clean combinatorial logic |
| Prefix Count Method | O(n) | O(1) | Useful when expressing the logic as prefix states or lightweight dynamic programming |
Leetcode Weekly contest 351 - Medium - Ways to Split Array Into Good Subarrays • Prakhar Agrawal • 1,847 views views
Watch 8 more video solutions →Practice Ways to Split Array Into Good Subarrays with our built-in code editor and test cases.
Practice on FleetCode