Problem Description

You are given an array nums of non-negative integers. Your task is to find the number of ways to split this array into three non-empty contiguous subarrays (called left, mid, and right from left to right) such that:

1. Each subarray must be non-empty and contiguous
2. The sum of elements in left ≤ the sum of elements in mid
3. The sum of elements in mid ≤ the sum of elements in right

For example, if you have an array [1, 2, 2, 2, 5, 0], you need to find all valid ways to place two split points that divide it into three parts where the sum increases (or stays equal) from left to right.

Since the total number of valid splits can be very large, return the result modulo 10^9 + 7.

The solution uses prefix sums combined with binary search. A prefix sum array s is created where s[i] represents the sum of elements from index 0 to i. For each possible ending position i of the left subarray, binary search finds:

• The leftmost valid starting position j for the right subarray (where s[j] - s[i] ≥ s[i])
• The rightmost valid starting position k for the right subarray (where s[n-1] - s[k] ≥ s[k] - s[i])

The number of valid splits with left ending at position i is k - j. The total count is the sum of all such valid splits across all possible positions of i.

Intuition

The key insight is that we need to find valid positions for two split points that divide the array into three parts with non-decreasing sums. Since we're dealing with non-negative integers, the prefix sum array will be monotonically non-decreasing, which opens the door for binary search optimization.

Let's think about this step by step. If we fix the ending position of the left subarray at index i, we need to find all valid positions where we can place the second split (between mid and right). For a position j to be valid as the start of the right subarray:

• The sum of mid (from i+1 to j-1) must be ≥ sum of left (from 0 to i)
• The sum of right (from j to n-1) must be ≥ sum of mid

Using prefix sums, these conditions translate to:

• s[j-1] - s[i] ≥ s[i], which simplifies to s[j-1] ≥ 2 * s[i]
• s[n-1] - s[j-1] ≥ s[j-1] - s[i], which simplifies to s[j-1] ≤ (s[n-1] + s[i]) / 2

Since the prefix sum array is sorted, for a fixed i, there exists a continuous range [j, k) where all positions satisfy both conditions. The leftmost valid position can be found using binary search for the smallest value ≥ 2 * s[i], and the rightmost valid position can be found by searching for the largest value ≤ (s[n-1] + s[i]) / 2.

This transforms our problem from checking every possible combination (which would be O(n²)) to efficiently finding valid ranges using binary search for each possible left endpoint, reducing the complexity to O(n log n).

Learn more about Two Pointers, Binary Search and Prefix Sum patterns.

Solution Approach

The implementation follows a prefix sum + binary search strategy:

Step 1: Build Prefix Sum Array

s = list(accumulate(nums))

We create a prefix sum array where s[i] represents the sum of elements from index 0 to i. This allows us to calculate any subarray sum in O(1) time: sum from index i to j equals s[j] - s[i-1].

Step 2: Enumerate Left Subarray Endpoints

for i in range(n - 2):

We iterate through all possible ending positions for the left subarray. We stop at n-2 because we need at least one element for mid and one for right.

Step 3: Find Valid Range for Right Subarray Start For each fixed left endpoint at position i:

• Find minimum valid position j:

  j = bisect_left(s, s[i] << 1, i + 1, n - 1)

  We need s[j] ≥ 2 * s[i] (written as s[i] << 1 for efficiency). This ensures the sum of mid is at least the sum of left. We search from i + 1 (after left ends) to n - 1.

• Find maximum valid position k:

  k = bisect_right(s, (s[-1] + s[i]) >> 1, j, n - 1)

  We need s[k] ≤ (s[n-1] + s[i]) / 2 (using >> 1 for integer division). This ensures the sum of right is at least the sum of mid. We search from j (the minimum valid position) to n - 1.

Step 4: Count Valid Splits

ans += k - j

The number of valid ways to place the second split with the first split after position i is k - j. Each index in the range [j, k) represents a valid starting position for the right subarray.

Step 5: Return Result with Modulo

return ans % mod

Since the answer can be large, we return it modulo 10^9 + 7.

The time complexity is O(n log n) where n is the length of the array - we iterate through n positions and perform two binary searches for each. The space complexity is O(n) for storing the prefix sum array.

Example Walkthrough

Let's walk through the solution with the array nums = [1, 2, 2, 2, 5, 0].

Step 1: Build Prefix Sum Array

nums = [1, 2, 2, 2, 5, 0]
s    = [1, 3, 5, 7, 12, 12]

Each element in s represents the cumulative sum up to that index.

Step 2: Iterate Through Possible Left Endpoints

Let's examine when i = 0 (left subarray is just [1]):

• Sum of left = s[0] = 1
• We need to find positions j where:
  • The mid subarray sum ≥ 1 (sum of left)
  • The right subarray sum ≥ mid subarray sum

Finding valid range for j:

• Minimum j: We need s[j] ≥ 2 * s[0] = 2 * 1 = 2

  • Using binary search from index 1 to 5: finds j = 1 (since s[1] = 3 ≥ 2)

• Maximum k: We need s[k] ≤ (s[5] + s[0]) / 2 = (12 + 1) / 2 = 6

  • Using binary search from index 1 to 5: finds k = 3 (since s[2] = 5 ≤ 6 but s[3] = 7 > 6)

Valid positions for second split: [1, 2] (k - j = 3 - 1 = 2 valid ways)

Let's verify these splits:

• Split at j=1: [1] | [2] | [2,2,5,0] → sums: 1, 2, 9 ✓ (1 ≤ 2 ≤ 9)
• Split at j=2: [1] | [2,2] | [2,5,0] → sums: 1, 4, 7 ✓ (1 ≤ 4 ≤ 7)

When i = 1 (left subarray is [1,2]):

• Sum of left = s[1] = 3
• Minimum j: Need s[j] ≥ 2 * 3 = 6, finds j = 3 (since s[3] = 7 ≥ 6)
• Maximum k: Need s[k] ≤ (12 + 3) / 2 = 7, finds k = 4 (since s[3] = 7 ≤ 7)

Valid positions: [3] (k - j = 4 - 3 = 1 valid way)

• Split at j=3: [1,2] | [2,2] | [5,0] → sums: 3, 4, 5 ✓ (3 ≤ 4 ≤ 5)

When i = 2 (left subarray is [1,2,2]):

• Sum of left = s[2] = 5
• Minimum j: Need s[j] ≥ 2 * 5 = 10, finds j = 4 (since s[4] = 12 ≥ 10)
• Maximum k: Need s[k] ≤ (12 + 5) / 2 = 8, but s[4] = 12 > 8

No valid positions (k < j), so 0 valid ways.

When i = 3 (left subarray is [1,2,2,2]):

• Sum of left = s[3] = 7
• Minimum j: Need s[j] ≥ 2 * 7 = 14, but max s[5] = 12 < 14

No valid positions, so 0 valid ways.

Total: 2 + 1 + 0 + 0 = 3 valid ways to split the array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n), where n is the length of the array nums.

• Creating the prefix sum array using accumulate(nums) takes O(n) time.
• The outer loop runs n - 2 times, iterating through each possible position for the first split.
• Inside each iteration:
  • bisect_left performs binary search on the prefix sum array, taking O(log n) time.
  • bisect_right performs binary search on the prefix sum array, taking O(log n) time.
• Therefore, the total time complexity is O(n - 2) × O(log n + log n) = O(n × log n).

Space Complexity: O(n)

• The prefix sum array s stores n elements, requiring O(n) space.
• Other variables (ans, i, j, k, mod) use constant space O(1).
• The overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Binary Search Boundaries

One of the most common mistakes is incorrectly setting the search boundaries for bisect_left and bisect_right.

Pitfall Example:

# Incorrect: searching up to n instead of n-1
min_j = bisect_left(prefix_sums, left_sum * 2, i + 1, n)  # Wrong!

Why it's wrong: The second split must leave at least one element for the right subarray. If we allow j to be n-1, then the right subarray would be empty.

Correct Solution:

# Correct: ensure at least one element remains for the right subarray
min_j = bisect_left(prefix_sums, left_sum * 2, i + 1, n - 1)

2. Integer Overflow When Calculating Middle Point

When finding the maximum valid position for the second split, we need to calculate (total_sum + left_sum) / 2.

Pitfall Example:

# Potential overflow in other languages, or precision issues with division
max_j = bisect_right(prefix_sums, (total_sum + left_sum) / 2, min_j, n - 1)  # Wrong!

Why it's wrong: Using regular division / returns a float, which can cause precision issues when comparing with integer prefix sums. Additionally, in languages like Java or C++, the sum might overflow.

Correct Solution:

# Use integer division to avoid precision issues
max_j = bisect_right(prefix_sums, (total_sum + left_sum) // 2, min_j, n - 1)
# Or use bit shift for efficiency
max_j = bisect_right(prefix_sums, (total_sum + left_sum) >> 1, min_j, n - 1)

3. Forgetting to Handle Edge Cases with Invalid Ranges

When min_j exceeds the valid range, we might still try to calculate max_j with invalid parameters.

Pitfall Example:

for i in range(n - 2):
    left_sum = prefix_sums[i]
    min_j = bisect_left(prefix_sums, left_sum * 2, i + 1, n - 1)
    max_j = bisect_right(prefix_sums, (total_sum + left_sum) // 2, min_j, n - 1)
    result += max_j - min_j  # Could be negative if min_j is out of bounds!

Correct Solution:

for i in range(n - 2):
    left_sum = prefix_sums[i]
    min_j = bisect_left(prefix_sums, left_sum * 2, i + 1, n - 1)
  
    # Check if min_j is within valid range
    if min_j < n - 1:
        max_j = bisect_right(prefix_sums, (total_sum + left_sum) // 2, min_j, n - 1)
        result += max_j - min_j

4. Misunderstanding the Inequality Conditions

The problem requires left_sum ≤ mid_sum ≤ right_sum. A common mistake is using strict inequalities or reversing the conditions.

Pitfall Example:

# Wrong: using strict inequality (should be ≤, not <)
min_j = bisect_left(prefix_sums, left_sum * 2 + 1, i + 1, n - 1)  # Wrong!

Correct Solution:

# Correct: finding the first position where prefix_sums[j] >= 2 * left_sum
min_j = bisect_left(prefix_sums, left_sum * 2, i + 1, n - 1)

5. Not Applying Modulo at the Right Time

While Python handles large integers well, forgetting to apply modulo can still cause issues in other languages or when the problem explicitly requires it.

Pitfall Example:

for i in range(n - 2):
    # ... calculation ...
    result += max_j - min_j
    result %= MOD  # Applying modulo inside the loop is inefficient

Correct Solution:

for i in range(n - 2):
    # ... calculation ...
    result += max_j - min_j

# Apply modulo once at the end (more efficient)
return result % MOD