Watch 9 video solutions for Ways to Split Array Into Good Subarrays, a medium level problem involving Array, Math, Dynamic Programming. This walkthrough by Prakhar Agrawal has 1,847 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |