{x}
blog image

Ways to Split Array Into Three Subarrays

A split of an integer array is good if:

  • The array is split into three non-empty contiguous subarrays - named left, mid, right respectively from left to right.
  • The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

 

Constraints:

  • 3 <= nums.length <= 105
  • 0 <= nums[i] <= 104

Solution Explanation: Ways to Split Array Into Three Subarrays

This problem asks us to find the number of ways to split an array into three non-empty contiguous subarrays (left, mid, right) such that the sum of elements in left is less than or equal to the sum of elements in mid, and the sum of elements in mid is less than or equal to the sum of elements in right.

The most efficient approach leverages prefix sums and binary search.

1. Prefix Sum:

We first calculate the prefix sum array s. s[i] represents the sum of elements from nums[0] to nums[i]. This allows us to efficiently calculate the sum of any subarray in O(1) time. For example, the sum of the subarray from index i to j (inclusive) is s[j] - s[i-1] (handling i=0 appropriately).

2. Iterative Approach with Binary Search:

The core idea is to iterate through all possible positions for the split between left and mid. For each such split (i):

  • Left Sum: The sum of left is s[i].

  • Finding mid and right: We need to find the valid range of indices (j, k) where j is the start of mid and k is the start of right.

    • Condition 1: sum(mid) >= sum(left): This implies s[j] - s[i] >= s[i]. We can efficiently find the smallest j satisfying this condition using binary search on the prefix sum array.

    • Condition 2: sum(right) >= sum(mid): This implies s[n-1] - s[k-1] >= s[k-1] - s[i], which simplifies to s[k-1] <= (s[n-1] + s[i]) / 2. Again, binary search helps to quickly find the largest k fulfilling this.

  • Counting Valid Splits: The number of valid splits for the current i is k - j. We accumulate this count in ans.

3. Time Complexity Analysis:

  • Prefix Sum Calculation: O(n)
  • Outer Loop (iterating through i): O(n)
  • Binary Search for j and k: O(log n) for each i

Therefore, the overall time complexity is O(n log n). The space complexity is O(n) due to the prefix sum array.

4. Code Implementation (Python):

import bisect
from itertools import accumulate
 
class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        s = list(accumulate(nums))
        ans, n = 0, len(nums)
        for i in range(n - 2):
            j = bisect_left(s, s[i] << 1, i + 1, n - 1)  # Binary search for j
            k = bisect_right(s, (s[-1] + s[i]) >> 1, j, n - 1)  # Binary search for k
            ans = (ans + k - j) % mod
        return ans

The other language implementations (Java, C++, Go, Javascript) follow the same algorithmic approach, differing only in syntax and library functions for binary search and prefix sum calculations. The core logic remains consistent.