LeetCode 2750 - Ways to Split Array Into Good Subarrays

The problem asks us to count the number of ways we can split a given binary array nums into contiguous subarrays such that each subarray contains exactly one 1. The input is a binary array, meaning it only contains 0s and 1s.

leetcodemediumarraymathdynamic-programming

LeetCode Problem 2750

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count the number of ways we can split a given binary array nums into contiguous subarrays such that each subarray contains exactly one 1. The input is a binary array, meaning it only contains 0s and 1s. The output is a single integer representing the number of valid splits, taken modulo $10^9 + 7$ because the result can be very large.

In other words, we need to partition the array around the 1s, allowing any number of 0s before and after each 1, but each partition must contain exactly one 1. A key observation is that the placement of 0s around the 1s determines how many ways we can split the array.

Constraints indicate that the array can be quite large, up to $10^5$ elements. This rules out naive combinatorial enumeration of all subarrays because the number of possible splits grows exponentially with the array size.

Important edge cases include arrays with:

  1. No 1s - in which case there are zero valid splits.
  2. Only 1s - each 1 must form its own subarray, but this also limits split choices.
  3. Consecutive 1s - splits must place each 1 in its own subarray, which affects counting.

Understanding these constraints and edge cases is crucial for designing an efficient solution.

Approaches

Brute Force

A brute-force approach would generate all possible ways to split the array into contiguous subarrays, then check each split to see if every subarray contains exactly one 1. While correct, this is highly inefficient because the number of splits grows exponentially with the array length. Even for moderate array sizes, this approach would be computationally infeasible.

Optimal Approach

The optimal approach is based on the insight that each 1 defines a subarray boundary. The key observation is that the number of ways to split the array between consecutive 1s is determined by the number of 0s separating them. Specifically, if there are k zeros between two 1s, there are k + 1 ways to assign these zeros to the left or right subarray.

Thus, the total number of splits is the product of (zeros_between_consecutive_1s + 1) across all consecutive 1s. If the array contains no 1s, the answer is 0. This method is linear because it requires a single pass to identify the 1s and count the zeros between them.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Generate all subarray splits and count valid ones
Optimal O(n) O(1) Count zeros between consecutive 1s and multiply, linear scan

Algorithm Walkthrough

  1. Initialize a variable mod to $10^9 + 7$ to handle large results.
  2. Iterate through the array and record the indices of all 1s in a list ones.
  3. If there are no 1s, return 0 because no good subarrays exist.
  4. Initialize ways to 1. This will store the running product of the number of choices for each split.
  5. For each pair of consecutive indices in ones, calculate the number of zeros between them (distance = ones[i] - ones[i-1] - 1).
  6. Multiply ways by distance + 1 (representing all possible ways to assign zeros to left or right subarray) and take modulo mod.
  7. Return ways.

Why it works: This works because each 1 must be in its own subarray. The zeros between consecutive 1s can be distributed in any way while maintaining the "exactly one 1 per subarray" constraint. Counting the choices for each pair of consecutive 1s and multiplying gives all valid combinations.

Python Solution

from typing import List

class Solution:
    def numberOfGoodSubarraySplits(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        ones = [i for i, num in enumerate(nums) if num == 1]
        if not ones:
            return 0

        ways = 1
        for i in range(1, len(ones)):
            distance = ones[i] - ones[i - 1] - 1
            ways = (ways * (distance + 1)) % mod

        return ways

Explanation: We first collect the indices of all 1s. If there are none, we immediately return 0. For every pair of consecutive 1s, we calculate the number of 0s between them and multiply the current count of ways by (distance + 1) modulo $10^9 + 7$. This efficiently calculates all possible valid splits.

Go Solution

func numberOfGoodSubarraySplits(nums []int) int {
    mod := int(1e9 + 7)
    ones := []int{}
    for i, num := range nums {
        if num == 1 {
            ones = append(ones, i)
        }
    }

    if len(ones) == 0 {
        return 0
    }

    ways := 1
    for i := 1; i < len(ones); i++ {
        distance := ones[i] - ones[i-1] - 1
        ways = (ways * (distance + 1)) % mod
    }

    return ways
}

Go-specific notes: The Go solution mirrors the Python logic closely. We use a slice to store indices of 1s. Since Go does not have built-in big integers by default, we rely on modulo arithmetic to prevent overflow. Slices are dynamic, so collecting indices is straightforward.

Worked Examples

Example 1

Input: [0,1,0,0,1]

Indices of 1s: [1, 4]

Distance between 1s: 4 - 1 - 1 = 2 zeros between them

Ways = 2 + 1 = 3

Output: 3

Example 2

Input: [0,1,0]

Indices of 1s: [1]

Only one 1, no splits needed, ways = 1

Output: 1

Step ones list distance ways
Initial [1,4] - 1
Pair 1 [1,4] 2 1 * (2+1) = 3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to find indices of 1s and calculate distances
Space O(n) Store indices of 1s (at most n elements)

The time complexity is linear since we only traverse the array twice (once to collect indices and once to calculate distances). Space complexity is also linear in the worst case when all elements are 1.

Test Cases

# provided examples
assert Solution().numberOfGoodSubarraySplits([0,1,0,0,1]) == 3  # example 1
assert Solution().numberOfGoodSubarraySplits([0,1,0]) == 1       # example 2

# edge cases
assert Solution().numberOfGoodSubarraySplits([0,0,0]) == 0        # no 1s
assert Solution().numberOfGoodSubarraySplits([1,1,1]) == 1        # consecutive 1s
assert Solution().numberOfGoodSubarraySplits([1,0,1,0,1]) == 4    # mix of zeros and ones
assert Solution().numberOfGoodSubarraySplits([1]) == 1            # single element
assert Solution().numberOfGoodSubarraySplits([0,1]) == 1          # one 1 at end
assert Solution().numberOfGoodSubarraySplits([1,0]) == 1          # one 1 at start
Test Why
[0,0,0] no 1s, should return 0
[1,1,1] consecutive 1s, only one way
[1,0,1,0,1] multiple zeros between 1s, check correct multiplication
[1] single element array
[0,1] 1 at the end, minimal case
[1,0] 1 at the start, minimal case

Edge Cases

No 1s in the array: Arrays like [0,0,0] cannot form any good subarray because each subarray must contain exactly one 1. Our solution detects this case by checking if the list of indices of 1s is empty and returns 0.

Consecutive 1s: Arrays like [1,1,1] have no zeros between 1s, so the number of ways to split is 1. Multiplying (distance + 1) with distance = 0 correctly yields 1 for each consecutive pair.

Single 1 in the array: Arrays like [0,1,0] or [1] only have one 1, so the only way to form a good subarray is the entire array itself. Our solution handles