#2750

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Ways to Split Array Into Good Subarrays

Calculate the number of ways to partition a binary array into good subarrays using state transition dynamic programming efficiently.

array math dynamic programming

Problem Statement

Given a binary array nums, a subarray is considered good if it contains exactly one element with the value 1. Determine how many ways the entire array can be split into consecutive good subarrays.

Return the total number of valid splits modulo 10^9 + 7. If the array contains only zeros, the result should be zero. Each split must maintain the original order and cover the entire array.

Examples

Example 1

Input: nums = [0,1,0,0,1]

Output: 3

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

There is 1 way to split nums into good subarrays:

[0,1,0]

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 1

Solution Approach

Identify positions of 1s

Traverse the array to record indices where nums[i] == 1. These positions determine the boundaries of potential good subarrays and allow calculation of distances between consecutive 1s for dynamic programming transitions.

Dynamic programming state definition

Define dp[i] as the number of ways to split the array up to the i-th 1. Use the distances between 1s to update dp[i] from dp[i-1] by multiplying the number of ways to partition the zeros between them, applying modulo 10^9 + 7.

Compute total splits

Iterate through all recorded 1 positions using the state transition formula to fill the dp array. The final dp value at the last 1 gives the total number of ways to split the array into good subarrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for a single pass to identify 1 positions and compute dp transitions. Space complexity is O(k) where k is the number of 1s, as we only store dp states and positions of 1s.

What Interviewers Usually Probe

Check for edge case when the array contains only zeros; answer should be 0.
Ask about handling large arrays and modulo operations to prevent integer overflow.
Probe understanding of state transition DP and distances between consecutive 1s.

Common Pitfalls or Variants

Common pitfalls

Forgetting to return 0 when there are no 1s in the array.
Incorrectly handling zeros at the beginning or end of the array in the DP calculation.
Neglecting the modulo operation, which can cause integer overflow for large arrays.

Follow-up variants

Allow subarrays to contain at most one 1 instead of exactly one 1, changing the DP transition rules.
Count splits where each good subarray contains exactly k ones, requiring generalized state transitions.
Consider arrays with more than two distinct values, extending the definition of good subarrays.

FAQ

What is the key pattern used in Ways to Split Array Into Good Subarrays?

The key pattern is state transition dynamic programming, where each dp state depends on distances between consecutive 1s.

How do I handle arrays that contain only zeros?

Return 0 immediately since there are no good subarrays possible if the array has no 1s.

Why do we apply modulo 10^9 + 7 in the solution?

Because the number of ways can be very large, modulo ensures results fit within integer limits.

Can this approach handle arrays up to length 10^5 efficiently?

Yes, identifying 1 positions and using state transition DP ensures an O(n) time solution suitable for large arrays.

What common mistake occurs in computing dp states?

A common mistake is miscounting the number of zeros between 1s or forgetting to multiply correctly for multiple partition options.

terminal

Solution

Solution 1: Multiplication Principle

Based on the problem description, we can draw a dividing line between two $1$s. Assuming the indices of the two $1$s 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 $1$s, it means there are no $1$s in the array, and the answer is $0$.

1

2

3

4

5

6

7

8

9

10

11

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 ans

Continue Practicing

#2681 power of heroes #2597 the number of beautiful subsets #2572 count the number of square free subsets