Ways to Split Array Into Three Subarrays: Prefix Sums + Binary Search

You are given an array nums of non-negative integers. You need to split it into three non-empty contiguous subarrays, called left, mid, and right, such that sum(left) <= sum(mid) <= sum(right). Return the number of valid ways to do this, modulo 10^9 + 7.

This is LeetCode 1712: Ways to Split Array Into Three Subarrays, and it is an excellent problem for combining two fundamental techniques: prefix sums and binary search. The approach it teaches shows up whenever you need to count valid partitions of an array under sum constraints.

Why this problem matters

A brute force approach that checks every pair of split points runs in O(n^2) time, which is too slow for the constraint of n up to 10^5. The trick is recognizing that once you fix the first split point, the valid positions for the second split point form a contiguous range. That range can be found efficiently with binary search.

This pattern of "fix one variable, binary search for the valid range of another" appears in many array partitioning and counting problems. Once you internalize the prefix sum + binary search combination here, you can apply the same framework to problems like "Split Array Largest Sum" (LeetCode 410) and "Divide Chocolate" (LeetCode 1231).

The key insight

Build a prefix sum array so you can compute the sum of any subarray in O(1). Then iterate over each possible first split point i. For a given i, the left subarray is nums[0..i] with sum prefix[i+1]. Now you need to find all valid second split points j (where i < j < n-1) such that:

1. sum(mid) >= sum(left): the middle subarray sum is at least as large as the left
2. sum(right) >= sum(mid): the right subarray sum is at least as large as the middle

Since the prefix sums are non-decreasing (all values are non-negative), both conditions define monotonic boundaries on j. You can binary search for the leftmost valid j and the rightmost valid j, then count the range.

The solution

from bisect import bisect_left, bisect_right

def waysToSplit(nums: list[int]) -> int:
    MOD = 10**9 + 7
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    total = prefix[n]
    result = 0

    for i in range(1, n - 1):
        left_sum = prefix[i]
        if left_sum * 3 > total:
            break

        lo = bisect_left(prefix, 2 * left_sum, i + 1, n)
        hi = bisect_right(prefix, (total + left_sum) // 2, i + 1, n) - 1

        if lo <= hi:
            result = (result + hi - lo + 1) % MOD

    return result

Let's walk through what each piece does.

First, we build the prefix sum array. prefix[i] stores the sum of nums[0..i-1], so the sum of any subarray nums[a..b] is prefix[b+1] - prefix[a].

The outer loop iterates over each possible first split point i. The left subarray is nums[0..i-1] with sum prefix[i]. We break early when left_sum * 3 > total, because if the left takes more than a third of the total, there is no way for mid and right to each be at least as large.

For the binary searches, we need to find the range of valid j values. The second split point j means mid is nums[i..j-1] with sum prefix[j] - prefix[i]. The conditions become:

• prefix[j] - prefix[i] >= prefix[i], which simplifies to prefix[j] >= 2 * left_sum. We use bisect_left to find the smallest such j.
• total - prefix[j] >= prefix[j] - prefix[i], which simplifies to prefix[j] <= (total + left_sum) / 2. We use bisect_right to find one past the largest such j, then subtract 1.

If the leftmost valid j is at most the rightmost valid j, the count of valid splits for this i is hi - lo + 1.

Visual walkthrough

Let's trace through nums = [1, 2, 2, 2, 5, 0] step by step. The total sum is 12, and the prefix array is [0, 1, 3, 5, 7, 12, 12].

For each first split point i, we binary search the prefix array to find the contiguous range of valid second split points j. When no valid range exists (because the left subarray is too large), we stop. The total count of valid splits is 4.

Complexity analysis

Time is O(n log n). We iterate over each possible first split point i (up to n iterations), and for each one we perform two binary searches on the prefix array (each O(log n)). The early termination when left_sum * 3 > total means we only iterate up to n/3 times in the worst case, but the dominant term is still O(n log n).

Space is O(n) for the prefix sum array. The input array itself is O(n), and we allocate one additional array of the same size. Everything else uses O(1) extra space.

The building blocks

1. Prefix sum array

The pattern of precomputing cumulative sums so that any subarray sum can be queried in O(1):

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + nums[i]

With this in place, the sum of nums[a..b] is prefix[b+1] - prefix[a]. This eliminates the need to re-sum subarrays from scratch each time you move a split point. You will use this pattern in nearly every problem that involves subarray sums, including "Subarray Sum Equals K," "Range Sum Query," and "Product of Array Except Self."

2. Binary search for boundaries

The pattern of using binary search to find the valid range of an index when the underlying sequence is monotonic:

lo = bisect_left(prefix, target_lo, start, end)
hi = bisect_right(prefix, target_hi, start, end) - 1
count = max(0, hi - lo + 1)

Because all values in nums are non-negative, the prefix sum array is non-decreasing. This monotonicity is what makes binary search valid here. bisect_left finds the first position where the condition is satisfied, and bisect_right finds one past the last position. The difference gives you the count of valid positions. This "binary search on a sorted prefix array" technique appears in problems like "Count of Range Sum" and "Split Array Largest Sum."

Edge cases

• All elements are zero: every split is valid. The count is (n-1) * (n-2) / 2 (choose 2 split points from n-1 gaps), modulo 10^9 + 7.
• Array of length 3: there is exactly one way to split (each subarray has one element). Valid only if nums[0] <= nums[1] <= nums[2].
• Descending array: if the array is sorted in decreasing order, no valid split may exist because sum(left) > sum(mid) for most split points.
• One very large element at the end: the right subarray dominates, so many splits become valid. The binary search range for j will be wide.
• All elements equal: similar to the all-zeros case, every split satisfying the position constraints is valid.
• Large n (10^5): the O(n log n) solution handles this comfortably within time limits.

From understanding to recall

You have seen how prefix sums turn subarray sum queries into O(1) lookups, and how binary search finds the valid range of split points in O(log n). The logic is clean: fix one split, binary search for the other, count the range. But reproducing the exact binary search targets under pressure is where people stumble.

Which prefix value do you compare against 2 * left_sum? Do you use bisect_left or bisect_right for the lower bound? What about the upper bound formula, is it (total + left_sum) / 2 or (total - left_sum) / 2? These details are not conceptual gaps. They are recall gaps, and they cost people offers.

Spaced repetition is how you close them. You practice building the prefix array, writing the binary search boundaries, and handling the modular arithmetic from memory at increasing intervals. After a few rounds, the derivation of prefix[j] >= 2 * left_sum becomes automatic. You see "split array into parts with sum constraints" in a problem description, and the prefix sum + binary search template flows out without hesitation.

Related posts

• Binary Search - The foundational technique behind finding valid split point ranges in sorted arrays
• Subarray Sum Equals K - Another prefix sum problem that counts subarrays satisfying a sum condition
• Split Array Largest Sum - A harder partitioning problem that also uses binary search, but on the answer space instead of indices

CodeBricks breaks Ways to Split Array Into Three Subarrays into its prefix sum and binary search building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a partitioning problem shows up in your interview, you do not think about it. You just write it.