Ways to Split Array Into Good Subarrays - Practice Coding Problems

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 10⁹ + 7.

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

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: There are 6 ways to split: [0,1]|[0,0,1]|[0,1], [0,1]|[0,0,1,0]|[1], [0,1,0]|[0,1]|[0,1], [0,1,0]|[0,1,0]|[1], [0,1,0,0]|[1]|[0,1], [0,1,0,0]|[1,0]|[1]

Example 2 — Single 1

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

› Output: 1

💡 Note: Only one way to split: [0,1,0] as a single subarray containing exactly one 1

Example 3 — No Valid Split

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

› Output: 0

💡 Note: Cannot create subarrays with exactly one 1 each - any split will have some subarray with 0 or multiple 1s

Constraints

1 ≤ nums.length ≤ 10⁵
nums[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Binary array [0,1,0,0,1,0,1]

Process

Find gaps between consecutive 1s

Output

Multiply gaps: 3 × 2 = 6 ways

Key Takeaway

🎯 Key Insight: The number of ways equals the product of gaps between consecutive 1s

Asked in

M Meta 15 G Google 12 M Microsoft 8

The key insight is that each split between consecutive 1s can be placed at multiple positions. The mathematical approach finds all 1 positions and multiplies the gaps between them. Best approach is Math: Time O(n), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Solution - Count Gaps Between 1s	O(n)	O(1)	Find positions of all 1s and multiply the gaps between consecutive 1s
Brute Force - Try All Split Combinations	O(2ⁿ × n)	O(n)	Generate all possible ways to split array and count valid ones

Mathematical Solution - Count Gaps Between 1s — Algorithm Steps

Find all positions where nums[i] = 1
Calculate gaps between consecutive 1s
Multiply all gap sizes to get total ways

Visualization

Tap to expand

Step-by-Step Walkthrough

Find 1s

Locate all positions containing '1'

Calculate Gaps

Count positions between consecutive 1s

Multiply

Product of all gaps gives total ways

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int solution(int* nums, int n) {
    // Find all positions of 1s
    int onesPositions[1000];
    int onesCount = 0;
    
    for (int i = 0; i < n; i++) {
        if (nums[i] == 1) {
            onesPositions[onesCount++] = i;
        }
    }
    
    // If no 1s, no valid splits possible
    if (onesCount == 0) {
        return 0;
    }
    
    // If only one 1, there's exactly one way
    if (onesCount == 1) {
        return 1;
    }
    
    // Calculate number of ways
    long long ways = 1;
    for (int i = 0; i < onesCount - 1; i++) {
        int gap = onesPositions[i + 1] - onesPositions[i];
        ways = (ways * gap) % MOD;
    }
    
    return ways;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to find 1s and calculate gaps

✓ Linear Growth

Space Complexity

O(1)

Only storing positions and counts, no extra data structures

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Solution - Count Gaps Between 1s — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler