Ways to Split Array Into Good Subarrays solution and explanation
8 more videos on this problem
Leetcode Weekly contest 351 - Medium - Ways to Split Array Into Good SubarraysPrakhar Agrawal · 6:50 · 1K views
Leetcode 2750 Ways to Split Array Into Good SubarraysThinkCode · 6:23 · 1K views
6910. Ways to Split Array Into Good Subarrays | Leetcode | Weekly Contest 351 | Sol Code In Comment.Optimization · 0:22 · 978 views
Bottom Up DP | 2750. Ways to Split Array Into Good Subarrays | Leetcode Weekly Contest 351codingMohan · 24:14 · 934 views
Ways to Split Array Into Good Subarrays LeetCode Weekly Contest 351 Join Link from commentsCoding Guru · 0:39 · 428 views
2750. Ways to Split Array Into Good Subarrays (Leetcode Medium)Programming Live with Larry · 11:59 · 314 views
Leetcode 2750 || Ways to Split Array Into Good Subarrays || Leetcode Weekly Medium || cppKomal Pal · 9:55 · 288 views
WAYS TO SPLIT ARRAY INTO GOOD SUBARRAYS | LEETCODE WEEKLY CONTEST 351 | LEETCODE | 6910 | #leetcodeTechRats official · 7:00 · 284 views
Leetcode 2750 Ways to Split Array Into Good SubarraysTech Diet · 10:39 · 125 views
The 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 <= 1050 <= nums[i] <= 1
Approach overview
Problem Overview: You are given a binary array and need to count how many ways it can be split into contiguous subarrays where each subarray contains exactly one 1. Zeros can appear anywhere inside a subarray, but every segment must include one and only one 1. The task reduces to counting valid split points between consecutive ones.
Approach 1: Gap Counting Method (O(n) time, O(1) space)
The key observation: every valid subarray must contain exactly one 1. That means splits can only occur between two consecutive 1 values. Count the number of zeros between each pair of ones. If there are k zeros between them, you have k + 1 possible places to split while still keeping one 1 per segment. Multiply these choices across all adjacent pairs of ones. Implementation is straightforward: iterate through the array, record the index of the previous 1, compute the gap when the next 1 appears, and multiply the answer by that gap size. If the array contains no 1, return 0 because forming a valid subarray is impossible. This solution uses simple arithmetic and a single pass, making it the most efficient approach for array problems involving binary structure.
Approach 2: Prefix Count Method (O(n) time, O(1) space)
This version frames the problem using running counts similar to lightweight dynamic programming. Track how many zeros appear after the previous 1. When a new 1 appears, those zeros represent multiple possible boundaries for the previous segment. Maintain a running number of valid splits and update it using multiplication with zeroCount + 1. Conceptually this treats each 1 as starting a new segment while the zeros between ones determine how many prefixes can form valid partitions. The logic is almost identical to the gap method but expressed through prefix tracking instead of explicit index gaps.
Both approaches rely on a simple combinatorial insight: the total number of valid splits equals the product of choices created by zeros between ones. The computation naturally fits problems combining math reasoning with linear array traversal.
Recommended for interviews: The Gap Counting Method is what interviewers typically expect. It shows you recognized the combinatorial structure of the array instead of brute‑forcing split positions. Explaining why each zero gap contributes gap + 1 choices demonstrates strong problem decomposition and leads directly to the optimal O(n) solution.
Approach 1: Gap Counting Method
This approach involves counting the zero gaps between consecutive `1`s. Each zero gap can provide a multiplicative factor to the number of ways we can split the array around `1`s to form good subarrays. To solve this, iterate through the `nums` array, and whenever a `1` is found, calculate the number of splits using zero gaps encountered so far and multiply this with the previous result. Track the zeros between `1`s using a counter.
def countGoodSubarrays(nums):
MOD = 10**9 + 7
count, ways, zero_count = 0, 1, 0
for num in nums:
if num == 1:
ways = (ways * (zero_count + 1)) % MOD
zero_count = 0
count += 1
else:
zero_count += 1
return ways if count > 0 else 0public class GoodSubarrays {
public int countGoodSubarrays(int[] nums) {
final int MOD = 1000000007;
int count = 0, ways = 1, zeroCount = 0;
for (int num : nums) {
if (num == 1) {
ways = (int)((long)ways * (zeroCount + 1) % MOD);
zeroCount = 0;
count++;
} else {
zeroCount++;
}
}
return count > 0 ? ways : 0;
}
}#include <vector>
using namespace std;
class Solution {
public:
int countGoodSubarrays(vector<int>& nums) {
const int MOD = 1000000007;
long long ways = 1, zeroCount = 0;
int count = 0;
for (int num : nums) {
if (num == 1) {
ways = (ways * (zeroCount + 1)) % MOD;
zeroCount = 0;
count++;
} else {
zeroCount++;
}
}
return count > 0 ? ways : 0;
}
};We initialize our main variables: `MOD` to handle modulo operation, `ways` to calculate the number of split ways, and `zero_count` to keep track of zeros between `1`s. As we iterate, each `1` encountered helps us accumulate the result by factoring in the preceding zeros. Finally, return `ways` if there is at least one `1` in the array.
Time Complexity: O(n) - since we only traverse the array once.
Space Complexity: O(1) - as we use a constant space to manage the counters.
Approach 2: Prefix Count Method
This approach leverages the counting of cumulative prefixes which might split into valid subarrays. By considering the prefix sums at each point, we deliberately choose indices to count potential good subarrays, focusing shifts for every `1` encountered.
function countGoodSubarrays(nums) {
const MOD = 10**9 + 7;
let ways = 1, zeroCount = 0;
for (let num of nums) {
if (num === 1) {
ways = ways * (zeroCount + 1) % MOD;
zeroCount = 0;
} else {
zeroCount++;
}
}
return (ways === 1) ? 0 : ways;
}public class Solution {
public int CountGoodSubarrays(int[] nums) {
const int MOD = 1000000007;
int ways = 1, zeroCount = 0;
foreach (var num in nums) {
if (num == 1) {
ways = (int)((long)ways * (zeroCount + 1) % MOD);
zeroCount = 0;
} else {
zeroCount++;
}
}
return ways == 1 ? 0 : ways;
}
}The JavaScript implementation aligns with the logic of leveraging prefix count and zero spans between `1`s. The calculations are wrapped efficiently within one loop using modulo to manage large results.
Time Complexity: O(n) - directly proportional to the length of nums.
Space Complexity: O(1) - due to constant space use.
Approach 3: Multiplication Principle
Based on the problem description, we can draw a dividing line between two 1s. Assuming the indices of the two 1s are j and i respectively, then the number of different dividing lines that can be drawn is i - j. We find all the pairs of j and i that meet the condition, and then multiply all the i - j together. If no dividing line can be found between two 1s, it means there are no 1s in the array, and the answer is 0.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function numberOfGoodSubarraySplits(nums: number[]): number {
let ans = 1;
let j = -1;
const mod = 10 ** 9 + 7;
const n = nums.length;
for (let i = 0; i < n; ++i) {
if (nums[i] === 0) {
continue;
}
if (j > -1) {
ans = (ans * (i - j)) % mod;
}
j = i;
}
return j === -1 ? 0 : ans;
}func numberOfGoodSubarraySplits(nums []int) int {
const mod int = 1e9 + 7
ans, j := 1, -1
for i, x := range nums {
if x == 0 {
continue
}
if j > -1 {
ans = ans * (i - j) % mod
}
j = i
}
if j == -1 {
return 0
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Gap Counting Method | Time Complexity: O(n) - since we only traverse the array once. |
| Prefix Count Method | Time Complexity: O(n) - directly proportional to the length of nums. |
| Multiplication Principle | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Gap Counting Method | O(n) | O(1) | Best general solution for binary arrays; minimal memory and clean combinatorial logic |
| Prefix Count Method | O(n) | O(1) | Useful when expressing the logic as prefix states or lightweight dynamic programming |
Frequently asked questions
Is Ways to Split Array Into Good Subarrays easy or hard?
The problem is rated Medium because the implementation is simple but the key insight is not immediately obvious. Recognizing that zeros between consecutive 1s create multiple valid split points is the main step needed to derive the optimal O(n) solution.
Ways to Split Array Into Good Subarrays Python/Java solution
Most implementations follow the same pattern across languages: iterate through the array, track the previous index of 1, compute the gap when the next 1 appears, and multiply the answer by that gap size. Python, Java, and C++ implementations typically complete this in under 10 lines using simple loops.
How to solve Ways to Split Array Into Good Subarrays in O(n)?
Traverse the array and track the index of each 1. For every pair of consecutive 1s, compute the distance between them, which represents the number of valid split points. Multiply these values across all pairs. This single-pass approach yields an O(n) time solution with constant extra space.
What is the best approach for Ways to Split Array Into Good Subarrays?
The Gap Counting Method is the most efficient and commonly used solution. It counts the number of zeros between consecutive 1s and multiplies the possible split choices. If there are k zeros between two 1s, you get k+1 ways to place a boundary. This produces an O(n) time and O(1) space solution.
Is Ways to Split Array Into Good Subarrays asked at Google/Amazon/Meta?
Problems combining array traversal with combinatorial counting appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test whether candidates recognize patterns in binary arrays and convert them into simple mathematical counts.
What data structure is used in Ways to Split Array Into Good Subarrays?
The solution primarily uses basic array traversal with a few integer counters. No advanced data structures are required. The core idea relies on mathematical counting of gaps between elements in a binary array.
What is the time complexity of Ways to Split Array Into Good Subarrays?
The optimal solution runs in O(n) time because the array is scanned once to locate the positions of 1s and compute the gaps between them. Space complexity is O(1) since only a few counters and the previous index of 1 are stored.