Ways to Split Array Into Good Subarrays — Medium Problem & Solution

Problem statement

nums is a binary array. A subarray is good if it contains exactly one element equal to 1.

Count the ways to split nums into consecutive non-empty good subarrays (every element belongs to exactly one piece, and every piece is good). Return the count modulo 10^9 + 7.

Example 1

Input: nums = [0,1,0,0,1]
Output: 3
Explanation: `[0,1] [0,0,1]`, `[0,1,0] [0,1]` and `[0,1,0,0] [1]`.

Example 2

Input: nums = [1,0,0,1,0,1]
Output: 6
Explanation: Three places to cut between the first two 1s, two between the last two.

Example 3

Input: nums = [0,0,0]
Output: 0
Explanation: No piece can contain a 1.

Constraints

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 1

How to solve Ways to Split Array Into Good Subarrays

The pieces are pinned by the 1s: the zeros before the first 1 and after the last 1 must join the first and last pieces, and the only freedom is where to cut inside each run of zeros between consecutive 1s.

Approach

1. Scan the array and remember the index prev of the previous 1.
2. At each new 1 at index i, multiply the answer by i - prev (mod 10^9 + 7).
3. If no 1 was seen, return 0; otherwise return the product (1 when there is a single 1).

Why it works

A split into good pieces is fully determined by choosing, for every pair of consecutive 1s at p < q, the position of the single cut between them, which may follow any of the q - p indices p..q-1. These choices are independent, so the count is their product.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• An array with no 1 gives 0, not 1.
• Leading and trailing zeros add no choices.
• Multiply in 64-bit before reducing: the running product is below 10^9 + 7 but one more factor can push it past 32 bits.

Reference solution

Python

from typing import List

def numberOfGoodSubarraySplits(nums: List[int]) -> int:
    MOD = 10**9 + 7
    ans = 1
    prev = -1
    for i, v in enumerate(nums):
        if v == 1:
            if prev >= 0:
                ans = ans * (i - prev) % MOD
            prev = i
    return ans if prev >= 0 else 0

JavaScript

var numberOfGoodSubarraySplits = function(nums) {
    var MOD = 1000000007;
    var ans = 1, prev = -1;
    for (var i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {
            // ans < 2^30 and the gap < 2^17, so the product stays exact in a double
            if (prev >= 0) ans = (ans * (i - prev)) % MOD;
            prev = i;
        }
    }
    return prev >= 0 ? ans : 0;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium