Ways to Split Array Into Three Subarrays
Description
Given nums, count ways to split it into three non-empty parts where each part's sum is in non-decreasing order. Return the result as an integer.
Examples
nums = [1,2,2,2,5,0]3Using prefix sums, for each left boundary, binary search finds valid mid boundaries where leftSum <= midSum <= rightSum. The three valid splits are: [1],[2,2,2,5,0], [1,2],[2,2,5,0], and [1,2,2],[2,5,0], each satisfying the non-decreasing sum condition.
nums = [0,3,3]1With array [0,3,3], there's only one way to split into three subarrays: [0], [3], [3]. The sums are left=0, mid=3, right=3. Since 0 ≤ 3 ≤ 3, this is a valid split.
nums = [1,1,1,1,1,1]3With array [1,1,1,1,1,1], the task requires find splits where left sum ≤ mid sum ≤ right sum. Valid splits include: [1],[1],[1,1,1,1] (sums: 1≤1≤4), [1],[1,1],[1,1,1] (sums: 1≤2≤3), [1],[1,1,1],[1,1] (sums: 1≤3≤2 - invalid), [1,1],[1],[1,1,1] (sums: 2≤1≤3 - invalid), [1,1],[1,1],[1,1] (sums: 2≤2≤2), and others. After checking all possibilities, exactly 10 splits satisfy the condition.
Constraints
- •
3 ≤ nums.length ≤ 10⁵