Ways to Split Array Into Good Subarrays
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to solve the problem. We define dp[i] as the number of ways to split the prefix of the array nums[0...i-1] into good subarrays. To compute dp[i], we look for all possible last good subarrays ending at i-1. If nums[j...i-1] is a good subarray, it contributes dp[j] ways to dp[i]. Summing these up for all valid j gives the value of dp[i]. The final answer is the value of dp[n].
Algorithm
- Create a prefix sum array
prefix_onesof sizen+1, whereprefix_ones[i]stores the count of1s innums[0...i-1]. - Create a DP array
dpof sizen+1, initialized to 0. Setdp[0] = 1to represent one way to partition an empty prefix (the empty partition). - Iterate
ifrom 1 ton:- Inside, iterate
jfrom 0 toi-1:- If
prefix_ones[i] - prefix_ones[j] == 1, it means the subarraynums[j...i-1]is a good subarray. - In this case, add
dp[j]todp[i], as the number of ways to splitnums[0...i-1]ending with the good subarraynums[j...i-1]is equal to the number of ways to split the prefixnums[0...j-1].
- If
- Inside, iterate
- Remember to perform all additions modulo
10^9 + 7. - The final answer is
dp[n], which represents the total number of ways to split the entire arraynums[0...n-1].
Walkthrough
The state dp[i] represents the number of ways to partition the subarray nums[0...i-1] into good subarrays. The final answer will be dp[n]. The base case is dp[0] = 1, representing one way to partition an empty array (the empty partition). The recurrence relation is dp[i] = sum(dp[j]) for all 0 <= j < i such that the subarray nums[j...i-1] is "good" (contains exactly one 1). To efficiently check if nums[j...i-1] is good, we can precompute a prefix sum array prefix_ones, where prefix_ones[k] stores the count of 1s in nums[0...k-1]. The number of 1s in nums[j...i-1] is then prefix_ones[i] - prefix_ones[j]. The algorithm iterates i from 1 to n, and for each i, it iterates j from 0 to i-1, checking the condition and updating dp[i]. If the array contains no 1s, this formulation correctly yields 0.
class Solution { public int numberOfGoodSubarraySplits(int[] nums) { int n = nums.length; long MOD = 1_000_000_007; int[] prefixOnes = new int[n + 1]; for (int i = 0; i < n; i++) { prefixOnes[i + 1] = prefixOnes[i] + nums[i]; } long[] dp = new long[n + 1]; dp[0] = 1; // Base case: one way to split an empty prefix for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { // Check if subarray nums[j...i-1] is good if (prefixOnes[i] - prefixOnes[j] == 1) { dp[i] = (dp[i] + dp[j]) % MOD; } } } return (int) dp[n]; }}Complexity
Time
O(N^2), due to the nested loops for computing the DP table. The outer loop runs N times and the inner loop runs up to N times.
Space
O(N), for the DP array `dp` and the `prefixOnes` array.
Trade-offs
Pros
It's a systematic way to solve the problem that builds the solution from smaller subproblems.
Guaranteed to find the correct answer if it runs within the time limit.
Cons
The O(N^2) time complexity is inefficient and will likely result in a 'Time Limit Exceeded' error for the given constraints (N up to 10^5).
Requires O(N) extra space for the DP table and the prefix sums array.
A more efficient approach comes from a combinatorial insight. A valid split of the array into good subarrays means each subarray contains exactly one 1. This implies that the splits must occur in the spaces between the 1s. The number of ways to place a split between two consecutive 1s at indices i and j is simply the number of positions available, which is j - i. The total number of ways is the product of these counts for all consecutive pairs of 1s.
Algorithm
- Create a list to store the indices of all
1s. - Iterate through
numsand populate this list. - If the list of indices is empty, it means there are no
1s, so return 0. - If the list has only one element, it means there is only one
1. The only way is to consider the whole array as one good subarray, so return 1. - Initialize a variable
waysto 1. - Iterate through the list of indices from the first element up to the second-to-last element.
- In each iteration
i, calculate the difference between the next index and the current index:gap = indices.get(i+1) - indices.get(i). - Multiply
waysbygap, taking the result modulo10^9 + 7:ways = (ways * gap) % MOD. - After the loop, return the final
ways.
Walkthrough
First, we handle the edge cases: if the array contains no 1s, no split is possible, so the answer is 0. If it contains only one 1, the only way is to take the whole array as a single good subarray, so the answer is 1. The core idea is to find the indices of all 1s in the array. We iterate through the array once to collect all indices where nums[i] == 1 into a list. Then, we iterate through this list of indices. For each pair of consecutive indices idx_prev and idx_curr, the number of ways to place a split between them is idx_curr - idx_prev. We multiply these counts together to get the total number of ways. Since the result can be large, we perform multiplication modulo 10^9 + 7.
import java.util.ArrayList;import java.util.List; class Solution { public int numberOfGoodSubarraySplits(int[] nums) { long MOD = 1_000_000_007; List<Integer> oneIndices = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (nums[i] == 1) { oneIndices.add(i); } } if (oneIndices.isEmpty()) { return 0; } long ways = 1; for (int i = 0; i < oneIndices.size() - 1; i++) { long gap = oneIndices.get(i + 1) - oneIndices.get(i); ways = (ways * gap) % MOD; } return (int) ways; }}Complexity
Time
O(N), as we iterate through the array once to find the indices and then iterate through the list of indices once. The size of the index list is at most N.
Space
O(K), where K is the number of `1`s in the array. In the worst case, if all elements are `1`s, the space complexity is O(N).
Trade-offs
Pros
Much more efficient than the naive DP, with O(N) time complexity.
The logic is intuitive and directly models the structure of the problem.
Cons
Requires O(K) extra space to store the indices of the
1s, where K is the number of1s. In the worst case, K can be equal to N.
This approach is an optimization of the two-pass method. Instead of storing all indices of 1s in a list first, we can calculate the product of gaps on the fly in a single pass through the array. This eliminates the need for extra storage for the indices, reducing the space complexity to constant.
Algorithm
- Initialize
ways = 1,last_one_index = -1, andMOD = 10^9 + 7. - Iterate through the array
numswith indexi. - If
nums[i] == 1:- If
last_one_indexis not -1 (i.e., this is not the first1found):- Calculate the gap:
gap = i - last_one_index. - Multiply
waysbygap:ways = (ways * gap) % MOD.
- Calculate the gap:
- Update
last_one_index = i.
- If
- After the loop, if
last_one_indexis still -1, it means there were no1s in the array. Return 0. - Otherwise, return
ways.
Walkthrough
We iterate through the array, keeping track of the index of the last 1 we encountered. When we find a 1, if it's not the very first 1 we've seen, we calculate the distance between its current index and the index of the previous 1. This distance represents the number of ways to place a split between these two 1s. We multiply our running total by this distance. We need to handle the initial state carefully. We can use a variable, say last_one_index, initialized to -1. When we find the first 1, we just record its index. For subsequent 1s, we calculate the gap and update last_one_index. If after iterating through the whole array no 1 was found, the answer is 0. Otherwise, the accumulated product is the answer. If only one 1 is found, the product loop is never entered, and the initial value of 1 is correctly returned.
class Solution { public int numberOfGoodSubarraySplits(int[] nums) { long MOD = 1_000_000_007; long ways = 1; int lastOneIndex = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] == 1) { if (lastOneIndex != -1) { long gap = i - lastOneIndex; ways = (ways * gap) % MOD; } lastOneIndex = i; } } if (lastOneIndex == -1) { return 0; // No '1's found in the array } return (int) ways; }}Complexity
Time
O(N), as we iterate through the input array only once.
Space
O(1), as we only use a few variables to store the running product and the last seen index, regardless of the input size.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
Simple and elegant implementation.
Cons
There are no significant cons to this approach as it is optimal in both time and space.
Solutions
Solution
public class Solution { public int NumberOfGoodSubarraySplits(int[] nums) { long ans = 1, j = -1; int mod = 1000000007; int n = nums.Length; for (int i = 0; i < n; ++i) { if (nums[i] == 0) { continue; } if (j > -1) { ans = ans * (i - j) % mod; } j = i; } return j == -1 ? 0 : (int) ans; }}class Solution {public int numberOfGoodSubarraySplits(int[] nums) { final int mod = (int)1 e9 + 7; int ans = 1, j = -1; for (int i = 0; i < nums.length; ++i) { if (nums[i] == 0) { continue; } if (j > -1) { ans = (int)((long)ans * (i - j) % mod); } j = i; } return j == -1 ? 0 : ans; }}class Solution {public: int numberOfGoodSubarraySplits(vector<int> &nums) { const int mod = 1e9 + 7; int ans = 1, j = -1; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == 0) { continue; } if (j > -1) { ans = 1LL * ans * (i - j) % mod; } j = i; } return j == -1 ? 0 : ans; }};class Solution: def numberOfGoodSubarraySplits(self, nums: List[int]) -> int: mod = 10 ** 9 + 7 ans, j = 1, - 1 for i, x in enumerate(nums): if x == 0: continue if j > - 1: ans = ans * (i - j) % mod j = i return 0 if j == - 1 else ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.