Problem

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 arraynums intogood subarrays. As the number may be too large, return it modulo 10^9 + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4

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 <= 10^5
  • 0 <= nums[i] <= 1

Solution

Method 1 – Count Gaps Between 1s

Intuition

Each split must occur between two 1s, and the number of ways to split is the product of the number of ways to split between each pair of 1s. For each gap of zeros between two 1s, we can split after any of the zeros, so the number of ways is (gap length + 1).

Approach

  1. Find the indices of all 1s in nums.
  2. If there are no 1s, return 0.
  3. For each pair of consecutive 1s, count the number of zeros between them, and multiply (gap + 1) to the answer.
  4. Return the answer modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int numberOfGoodSubarraySplits(vector<int>& nums) {
        const int MOD = 1e9+7;
        vector<int> pos;
        for (int i = 0; i < nums.size(); ++i) if (nums[i] == 1) pos.push_back(i);
        if (pos.empty()) return 0;
        long long ans = 1;
        for (int i = 1; i < pos.size(); ++i) ans = ans * (pos[i] - pos[i-1]) % MOD;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func numberOfGoodSubarraySplits(nums []int) int {
    const mod = 1_000_000_007
    pos := []int{}
    for i, v := range nums {
        if v == 1 {
            pos = append(pos, i)
        }
    }
    if len(pos) == 0 {
        return 0
    }
    ans := 1
    for i := 1; i < len(pos); i++ {
        ans = ans * (pos[i] - pos[i-1]) % mod
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import java.util.*;
class Solution {
    public int numberOfGoodSubarraySplits(int[] nums) {
        int mod = 1_000_000_007;
        List<Integer> pos = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) if (nums[i] == 1) pos.add(i);
        if (pos.isEmpty()) return 0;
        long ans = 1;
        for (int i = 1; i < pos.size(); i++) ans = ans * (pos.get(i) - pos.get(i-1)) % mod;
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun numberOfGoodSubarraySplits(nums: IntArray): Int {
        val mod = 1_000_000_007
        val pos = mutableListOf<Int>()
        for (i in nums.indices) if (nums[i] == 1) pos.add(i)
        if (pos.isEmpty()) return 0
        var ans = 1L
        for (i in 1 until pos.size) ans = ans * (pos[i] - pos[i-1]) % mod
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from typing import List
class Solution:
    def numberOfGoodSubarraySplits(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        pos = [i for i, v in enumerate(nums) if v == 1]
        if not pos:
            return 0
        ans = 1
        for i in range(1, len(pos)):
            ans = ans * (pos[i] - pos[i-1]) % MOD
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn number_of_good_subarray_splits(nums: Vec<i32>) -> i32 {
        let m = 1_000_000_007;
        let pos: Vec<_> = nums.iter().enumerate().filter(|&(_, &v)| v == 1).map(|(i, _)| i).collect();
        if pos.is_empty() { return 0; }
        let mut ans = 1i64;
        for i in 1..pos.len() {
            ans = ans * (pos[i] - pos[i-1]) as i64 % m;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    numberOfGoodSubarraySplits(nums: number[]): number {
        const mod = 1_000_000_007;
        const pos: number[] = [];
        for (let i = 0; i < nums.length; i++) if (nums[i] === 1) pos.push(i);
        if (pos.length === 0) return 0;
        let ans = 1;
        for (let i = 1; i < pos.length; i++) ans = ans * (pos[i] - pos[i-1]) % mod;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once to find 1s and once to compute the answer.
  • 🧺 Space complexity: O(n) — For storing the positions of 1s.