Ways to split array into three subarrays

Array Two Pointers Binary Search Prefix Sum

34.2% acceptance

Feb 25, 2026

1504

110

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn ways_to_split(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + nums[i] as i64;
    }
    let total = prefix[n];
    let mut ans = 0i64;
    for i in 0..n - 2 {
      let ls = prefix[i + 1];
      if 3 * ls > total { break; }
      let lo = {
        let target = 2 * ls;
        let (mut a, mut b) = (i + 1, n - 1);
        while a < b {
          let m = a + (b - a) / 2;
          if prefix[m + 1] >= target { b = m; } else { a = m + 1; }
        }
        if prefix[a + 1] < target { n } else { a }
      };
      if lo >= n - 1 { continue; }
      let hi = {
        let target = total + ls;
        let (mut a, mut b) = (i + 1, n - 1);
        while a < b {
          let m = a + (b - a + 1) / 2;
          if 2 * prefix[m + 1] <= target { a = m; } else { b = m - 1; }
        }
        if 2 * prefix[a + 1] > target { 0 } else { a }
      };
      let hi = hi.min(n - 2);
      if lo <= hi {
        ans = (ans + (hi - lo + 1) as i64) % MOD;
      }
    }
    ans as i32
  }
}