2750. Ways to Split Array Into Good Subarrays

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

Solution (Java)

class Solution {
  private static final int modulo = (int) 1e9 + 7;

  public int numberOfGoodSubarraySplits(int[] nums) {
    final int n = nums.length;
    long count = 0;

    // find the first one
    int i = 0;
    while (i < n && nums[i] != 1) {
      i++;
    }

    if (i < n) {
      count++;
    }

    for (int j = i + 1; j < n; j++) {
      while (j < n && nums[j] == 0) {
        j++;
      }

      if (j < n && nums[j] == 1) {
        // we have j - i cuts with zero between two one(i, j)
        // 10...01
        // i ... j
        count = count * (j - i) % modulo;
        i = j;
      }
    }

    return (int) count;
  }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).