Ways to Split Array Into Good Subarrays - Solution & Explanation
Problem Statement
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] <= 1
Approach Overview
Problem 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 1: Gap Counting Method
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.
Complexity
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.
Approach 2: Prefix Count Method
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.
Code
C#
JavaScript
Complexity
Time Complexity: O(n) - single traversal executes over the array.
Space Complexity: O(1) - non-growing storage usage.
Approach 3: Multiplication Principle
Based on the problem description, we can draw a dividing line between two 1s. Assuming the indices of the two 1s are j and i respectively, then the number of different dividing lines that can be drawn is i - j. We find all the pairs of j and i that meet the condition, and then multiply all the i - j together. If no dividing line can be found between two 1s, it means there are no 1s in the array, and the answer is 0.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Complexity Comparison
| 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. |
| Multiplication Principle | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode Weekly contest 351 - Medium - Ways to Split Array Into Good Subarrays • Prakhar Agrawal • 1,848 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Ways to Split Array Into Good Subarrays easy or hard?
Ways to Split Array Into Good Subarrays Python/Java solution
How to solve Ways to Split Array Into Good Subarrays in O(n)?
What is the best approach for Ways to Split Array Into Good Subarrays?
Is Ways to Split Array Into Good Subarrays asked at Google/Amazon/Meta?
What data structure is used in Ways to Split Array Into Good Subarrays?
What is the time complexity of Ways to Split Array Into Good Subarrays?
Ready to solve this problem?
Practice Ways to Split Array Into Good Subarrays with our built-in code editor and test cases.
Practice on FleetCode