Problem Description
Given a binary array nums, a subarray is called good if it contains exactly one occurrence of the element 1. The task is to determine the number of ways to split the array into contiguous non-empty subarrays such that every subarray is good. Since the answer may be large, return it modulo 10^9 + 7.
Key Insights
- Every good subarray must contain exactly one 1.
- The positions of 1s in the array dictate how the splits must occur.
- When you have k ones, the array must be split into exactly k segments, each containing one 1.
- The number of ways to split the array is determined by the gaps between consecutive 1s. Specifically, if the ones occur at positions pos[0], pos[1], …, pos[k-1], then the number of ways equals the product for each gap: (pos[i] - pos[i-1]) for i from 1 to k-1.
- If there are no 1s, then it is impossible to form a good subarray, so the answer is 0.
Space and Time Complexity
Time Complexity: O(n), where n is the length of the nums array, since we iterate through the array to collect the positions of 1s. Space Complexity: O(n) in the worst-case scenario (if all elements are 1), due to the storage for indices of 1s.
Solution
The algorithm begins by scanning the array to record the indices where the element equals 1. If no such index is found, the answer is 0 because every subarray must contain one 1. Otherwise, the array must be divided into segments that each contain one 1. The number of valid splits is determined by the number of zeros between consecutive 1s. For each adjacent pair of ones at positions pos[i-1] and pos[i], any split that occurs between these positions is valid, and there are (pos[i] - pos[i-1]) choices. The final answer is the product of these choices modulo 10^9 + 7.