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] <= 1In #2750 Ways to Split Array Into Good Subarrays, the array contains only 0s and 1s, and a subarray is considered good if it contains exactly one 1. The task is to determine how many ways the array can be split so that every resulting subarray satisfies this condition.
A useful observation is that each valid segment must contain one 1, so the positions of 1s drive the structure of the solution. If there are no 1s, forming a valid partition is impossible. Otherwise, the number of valid splits depends on the number of 0s between consecutive 1s. Each gap provides multiple choices for where the boundary between subarrays can be placed.
By scanning the array and tracking the distance between consecutive 1s, we can multiply the number of choices contributed by each gap. This leads to a simple linear-time counting strategy that avoids explicitly generating partitions. The result is typically computed with modulo arithmetic to handle large outputs.
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Linear scan with gap counting between consecutive 1s | O(n) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
If the array consists of only 0s answer is 0.
In the final split, exactly one separation point exists between two consecutive 1s.
In how many ways can separation points be put?
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems with similar counting patterns and array observations frequently appear in FAANG-style interviews. They test the ability to recognize structural properties of arrays and convert them into efficient mathematical or dynamic programming solutions.
No complex data structure is required for this problem. A simple linear traversal with a few variables to track previous 1 positions and the running product is sufficient. This keeps the solution both time and space efficient.
The optimal approach scans the array and focuses on the positions of the 1s. The number of ways to split depends on the gaps between consecutive 1s, since each gap provides multiple valid boundary choices. Multiplying these choices while traversing the array gives the final count in linear time.
Zeros between two 1s determine how many places you can split the array while ensuring each segment still contains exactly one 1. Each zero increases the number of possible split boundaries between those two 1s, which contributes multiplicatively to the total number of ways.