LeetCode 1712 - Ways to Split Array Into Three Subarrays

LeetCode Problem 1712

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Prefix Sum

Solution

Problem Understanding

The problem asks us to count the number of valid ways to divide an array into three contiguous, non-empty parts:

• left
• mid
• right

The split must satisfy two conditions:

1. sum(left) <= sum(mid)
2. sum(mid) <= sum(right)

The array contains only non-negative integers, which is an extremely important property because prefix sums become monotonic. That monotonic behavior allows binary search or two pointer techniques to work efficiently.

A split is defined by choosing two cut positions:

• The first cut separates left and mid
• The second cut separates mid and right

If the array length is n, then:

• left uses indices [0 ... i]
• mid uses indices [i+1 ... j]
• right uses indices [j+1 ... n-1]

All three subarrays must contain at least one element, so:

• i >= 0
• j > i
• j < n - 1

The constraints are large:

• n can be up to 10^5

This immediately tells us that cubic or quadratic enumeration will not be fast enough. We need something close to O(n log n) or O(n).

Because all numbers are non-negative, prefix sums are non-decreasing. This is the key observation that enables efficient searching for valid split ranges.

Some important edge cases include:

• Arrays where no valid split exists
• Arrays containing many zeros
• Arrays where every split is valid
• Very small arrays of length 3
• Large arrays where brute force would time out

The problem guarantees non-negative integers, which is critical for the monotonic behavior used by the optimal solution.

Approaches

Brute Force Approach

The most direct solution is to try every possible pair of split points.

For every possible first cut i, we try every possible second cut j, then compute:

• leftSum
• midSum
• rightSum

If both required inequalities hold, we increment the answer.

Using prefix sums, each range sum can be computed in O(1), but there are still O(n^2) possible split pairs.

With n = 10^5, this becomes far too slow because:

10^5 * 10^5 = 10^10

operations are infeasible.

Optimal Approach

The key insight is that for a fixed left subarray, the valid range of mid boundaries forms a contiguous interval.

Since all numbers are non-negative:

• Prefix sums are sorted in non-decreasing order
• Increasing the second cut increases midSum
• Increasing the second cut decreases rightSum

This creates monotonic conditions that can be searched efficiently.

For every first split position i, we want to find:

• The smallest j where midSum >= leftSum
• The largest j where midSum <= rightSum

All indices between those two boundaries are valid.

We can find these boundaries efficiently using binary search on the prefix sum array.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Tries every pair of split positions
Optimal	O(n log n)	O(n)	Uses prefix sums with binary search

Algorithm Walkthrough

Step 1: Build Prefix Sums

Create a prefix sum array where:

prefix[i] = sum(nums[0...i])

This allows constant time subarray sum computation.

For example:

nums = [1,2,2,2,5,0]

prefix = [1,3,5,7,12,12]

Step 2: Iterate Over the First Split

Choose the end index i of the left subarray.

Since all three subarrays must be non-empty:

i ranges from 0 to n - 3

For each i:

leftSum = prefix[i]

Step 3: Find the Minimum Valid Second Split

We need:

midSum >= leftSum

Using prefix sums:

prefix[j] - prefix[i] >= prefix[i]

Rearranging:

prefix[j] >= 2 * prefix[i]

We binary search for the first index j satisfying this condition.

Step 4: Find the Maximum Valid Second Split

We also need:

midSum <= rightSum

Using prefix sums:

prefix[j] - prefix[i] <= totalSum - prefix[j]

Rearranging:

2 * prefix[j] <= totalSum + prefix[i]

We binary search for the last index j satisfying this condition.

Step 5: Count Valid Splits

If:

leftBound <= rightBound

then the number of valid splits is:

rightBound - leftBound + 1

Add this to the answer modulo 10^9 + 7.

Why it works

For a fixed left boundary, the conditions on mid produce a contiguous valid range because prefix sums are monotonic.

• Once midSum >= leftSum becomes true, it stays true
• Once midSum > rightSum becomes true, it remains invalid afterward

Therefore, all valid second split positions lie within one continuous interval, which binary search can locate efficiently.

Python Solution

from bisect import bisect_left, bisect_right
from typing import List

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)

        prefix = [0] * n
        prefix[0] = nums[0]

        for i in range(1, n):
            prefix[i] = prefix[i - 1] + nums[i]

        total_sum = prefix[-1]
        answer = 0

        for i in range(n - 2):
            left_sum = prefix[i]

            min_j = bisect_left(prefix, 2 * left_sum, i + 1, n - 1)

            max_target = (total_sum + left_sum) // 2
            max_j = bisect_right(prefix, max_target, min_j, n - 1) - 1

            if min_j <= max_j:
                answer += (max_j - min_j + 1)

        return answer % MOD

The implementation begins by constructing the prefix sum array. This allows every subarray sum to be represented using simple arithmetic instead of repeatedly summing ranges.

The loop iterates through every possible ending index of the left subarray. For each one, the algorithm computes the minimum and maximum valid positions for the second split.

bisect_left is used to find the first valid j where:

prefix[j] >= 2 * left_sum

This ensures:

midSum >= leftSum

Next, bisect_right finds the largest valid j satisfying:

2 * prefix[j] <= total_sum + left_sum

Every index inside that range produces a valid split, so the algorithm adds the size of the interval to the answer.

Finally, the result is returned modulo 10^9 + 7.

Go Solution

package main

import "sort"

func waysToSplit(nums []int) int {
	const MOD int = 1e9 + 7

	n := len(nums)

	prefix := make([]int, n)
	prefix[0] = nums[0]

	for i := 1; i < n; i++ {
		prefix[i] = prefix[i-1] + nums[i]
	}

	totalSum := prefix[n-1]
	answer := 0

	for i := 0; i < n-2; i++ {
		leftSum := prefix[i]

		minJ := sort.Search(n-1-(i+1), func(k int) bool {
			j := k + i + 1
			return prefix[j] >= 2*leftSum
		}) + i + 1

		maxTarget := (totalSum + leftSum) / 2

		maxJ := sort.Search(n-1-minJ, func(k int) bool {
			j := k + minJ
			return prefix[j] > maxTarget
		}) + minJ - 1

		if minJ <= maxJ {
			answer = (answer + (maxJ - minJ + 1)) % MOD
		}
	}

	return answer
}

The Go implementation follows the same algorithmic structure as the Python version.

Since Go does not provide built-in bisect utilities like Python, the solution uses sort.Search to implement binary search behavior.

Integer arithmetic is safe because the constraints keep prefix sums within the range of Go's int type on modern platforms.

Slices are used for the prefix sum array, and all computations remain iterative with no recursion.

Worked Examples

Example 1

nums = [1,1,1]

Prefix sums:

[1,2,3]

i	leftSum	Valid j Range	Count
0	1	j = 1	1

Result:

1

Example 2

nums = [1,2,2,2,5,0]

Prefix sums:

[1,3,5,7,12,12]

Total sum:

12

First split: i = 0

left = [1]
leftSum = 1

Need:

prefix[j] >= 2

First valid:

j = 1

Need:

2 * prefix[j] <= 13

Largest valid:

j = 2

Valid splits:

j = 1
j = 2

Count = 2

First split: i = 1

left = [1,2]
leftSum = 3

Need:

prefix[j] >= 6

First valid:

j = 3

Need:

2 * prefix[j] <= 15

Largest valid:

j = 3

Count = 1

First split: i = 2

leftSum = 5

No valid second split exists.

Total:

2 + 1 = 3

Example 3

nums = [3,2,1]

Prefix sums:

[3,5,6]

For i = 0:

leftSum = 3

Need:

prefix[j] >= 6

No valid j before the final element.

Result:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each iteration performs two binary searches
Space	O(n)	Prefix sum array storage

The algorithm iterates through all possible first split positions once. For each position, it performs two binary searches on the prefix sum array.

Since binary search costs O(log n) and there are n iterations, the total complexity becomes:

O(n log n)

The prefix sum array requires linear extra space.

Test Cases

from typing import List

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        from bisect import bisect_left, bisect_right

        MOD = 10**9 + 7
        n = len(nums)

        prefix = [0] * n
        prefix[0] = nums[0]

        for i in range(1, n):
            prefix[i] = prefix[i - 1] + nums[i]

        total_sum = prefix[-1]
        answer = 0

        for i in range(n - 2):
            left_sum = prefix[i]

            min_j = bisect_left(prefix, 2 * left_sum, i + 1, n - 1)

            max_target = (total_sum + left_sum) // 2
            max_j = bisect_right(prefix, max_target, min_j, n - 1) - 1

            if min_j <= max_j:
                answer += (max_j - min_j + 1)

        return answer % MOD

sol = Solution()

assert sol.waysToSplit([1,1,1]) == 1  # smallest valid case
assert sol.waysToSplit([1,2,2,2,5,0]) == 3  # example with multiple splits
assert sol.waysToSplit([3,2,1]) == 0  # no valid split
assert sol.waysToSplit([0,0,0]) == 1  # all zero values
assert sol.waysToSplit([0,0,0,0]) == 3  # many valid zero splits
assert sol.waysToSplit([1,1,1,1]) == 1  # only one balanced split
assert sol.waysToSplit([1,2,3,4,5]) == 3  # increasing sequence
assert sol.waysToSplit([5,0,0,0,0]) == 0  # large left prevents valid split
assert sol.waysToSplit([0,1,0,1,0]) >= 0  # mixed zeros and positives
assert sol.waysToSplit([10000] * 1000) >= 0  # stress test with large values

Test Summary

Test	Why
[1,1,1]	Smallest valid input
[1,2,2,2,5,0]	Standard example with multiple answers
[3,2,1]	No valid split exists
[0,0,0]	All sums equal
[0,0,0,0]	Multiple zero-based splits
[1,1,1,1]	Tight boundary conditions
[1,2,3,4,5]	Increasing prefix sums
[5,0,0,0,0]	Impossible due to oversized left sum
[0,1,0,1,0]	Mixed zeros and positives
[10000] * 1000	Stress and performance validation

Edge Cases

One important edge case is when all values are zero. In this situation, every subarray sum is zero, so both inequalities always hold. A naive implementation can accidentally miss valid ranges because many prefix sums are identical. The binary search based solution handles this correctly because it searches inclusive ranges over non-decreasing prefix sums.

Another critical case occurs when the first section becomes too large. For example:

[5,0,0,0,0]

Once leftSum exceeds what the remaining array can support, there are no valid second split positions. The binary searches naturally return an empty interval, and the implementation correctly adds zero to the answer.

A third important edge case is the smallest possible array length:

n = 3

There is exactly one possible split configuration. Incorrect boundary handling can accidentally allow empty subarrays or produce out-of-range binary search intervals. The implementation avoids this by iterating only until n - 2 and restricting the second split to occur before the final element.

Another subtle case involves duplicate prefix sums caused by zeros inside the array. Since multiple valid split positions may share the same prefix sum value, it is important to use:

• bisect_left for the first valid index
• bisect_right for the last valid index

Using the wrong binary search variant can undercount or overcount valid splits.