248. Good Ways to Split an Array in 3 Contiguous Parts

Good Ways to Split an Array in 3 Contiguous Parts

You are given a List<Integer> nums containing non-negative integers. Split the list into three non-empty contiguous parts: A1, A2, and A3.

Let:

S1 be the sum of elements in A1
S2 be the sum of elements in A2
S3 be the sum of elements in A3

Count how many splits are valid such that:

S2 ≤ S1 + S3

Return the count modulo 1,000,000,007.

Method Signature

int countGoodSplits(List<Integer> nums)

nums: a list of non-negative integers
Returns the number of valid ways to split nums into three non-empty contiguous parts
The returned value must be modulo 1,000,000,007

Valid Split Rules

A1, A2, and A3 must all be non-empty
The three parts must be contiguous
The original order of elements must not be changed
Every element of nums must belong to exactly one of the three parts
A split is valid only if S2 ≤ S1 + S3

Constraints

3 ≤ nums.size() ≤ 100,000
0 ≤ nums.get(i) ≤ 1,000,000
0 ≤ i < nums.size()
The answer must be returned modulo 1,000,000,007

Examples

Example 1

countGoodSplits(nums = List.of(1, 2, 1, 2))

Output:

3

Explanation:

[1], [2], [1, 2]: S2 = 2, S1 + S3 = 1 + 3 = 4, valid
[1], [2, 1], [2]: S2 = 3, S1 + S3 = 1 + 2 = 3, valid
[1, 2], [1], [2]: S2 = 1, S1 + S3 = 3 + 2 = 5, valid

Example 2

countGoodSplits(nums = List.of(5, 10, 5))

Output:

1

Explanation:

The only possible split is [5], [10], [5]
S2 = 10 and S1 + S3 = 5 + 5 = 10
Since 10 ≤ 10, the split is valid

Example 3

countGoodSplits(nums = List.of(1, 10, 1, 1))

Output:

1

Explanation:

[1], [10], [1, 1]: S2 = 10, S1 + S3 = 1 + 2 = 3, invalid
[1], [10, 1], [1]: S2 = 11, S1 + S3 = 1 + 1 = 2, invalid
[1, 10], [1], [1]: S2 = 1, S1 + S3 = 11 + 1 = 12, valid

Deterministic Output

The method should return only the final count of valid splits modulo 1,000,000,007. No split list needs to be returned. Therefore, the output is always deterministic.