# Ways to Split Array Into Three Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/ways-to-split-array-into-three-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/ways-to-split-array-into-three-subarrays
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Tekion](https://scaleengineer.com/companies/tekion), [Robinhood](https://scaleengineer.com/companies/robinhood)
---
## Problem
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`

# Approaches
## Brute Force with Prefix Sums
This approach iterates through all possible ways to split the array into three non-empty parts. A split is defined by two indices, `i` and `j`, where the first subarray ends at `i-1` and the second ends at `j-1`. We can use nested loops to check every valid pair of `(i, j)`. To make the sum calculation efficient, we first compute a prefix sum array. This allows us to find the sum of any subarray in constant time. For each pair of `(i, j)`, we calculate the sums of the `left`, `mid`, and `right` subarrays and check if they satisfy the required conditions.
**Time:** O(n^2) due to the nested loops iterating through all possible pairs of split points `(i, j)`. The prefix sum calculation takes O(n). · **Space:** O(n) to store the prefix sum array.
**Pros:** Simple to understand and implement.; Correctly solves the problem for smaller input sizes.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The core idea is to exhaustively check every possible pair of split points. Let the array `nums` have length `n`. A split is determined by two indices, `i` and `j`, which represent the end of the `left` subarray and the end of the `mid` subarray, respectively. The `left` part is `nums[0...i-1]`, `mid` is `nums[i...j-1]`, and `right` is `nums[j...n-1]`. To ensure all three subarrays are non-empty, `i` must be at least 1, and `j` must be at least `i+1`. Also, `j` must be less than `n` to leave a non-empty `right` part. This gives us the loop bounds: `i` from `1` to `n-2` and `j` from `i+1` to `n-1`.

To avoid re-calculating sums repeatedly, which would lead to an O(n^3) solution, we pre-compute a prefix sum array. Let `prefix[k]` be the sum of elements from `nums[0]` to `nums[k-1]`. Then, `sum(left) = prefix[i]`, `sum(mid) = prefix[j] - prefix[i]`, and `sum(right) = prefix[n] - prefix[j]`. With these O(1) sum calculations, the overall complexity is dominated by the nested loops, resulting in O(n^2).

```java
class Solution {
    public int waysToSplit(int[] nums) {
        int n = nums.length;
        int MOD = 1_000_000_007;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        long count = 0;
        // i is the first split point (exclusive), left part is [0, i-1]
        for (int i = 1; i < n; i++) {
            // j is the second split point (exclusive), mid part is [i, j-1]
            for (int j = i + 1; j < n; j++) {
                int sum_left = prefix[i];
                int sum_mid = prefix[j] - prefix[i];
                int sum_right = prefix[n] - prefix[j];

                if (sum_left <= sum_mid && sum_mid <= sum_right) {
                    count++;
                }
            }
        }

        return (int) (count % MOD);
    }
}
```
### Algorithm
- Pre-calculate a prefix sum array, `prefix`, where `prefix[k]` stores the sum of the first `k` elements of `nums`.
- Initialize a counter `count` to 0.
- Use two nested loops to iterate through all possible split points `i` and `j`.
  - The outer loop for the first split point `i` runs from `1` to `n-2`.
  - The inner loop for the second split point `j` runs from `i+1` to `n-1`.
- Inside the inner loop, calculate the sums of the three subarrays (`left`, `mid`, `right`) in O(1) time using the prefix sum array:
  - `sum_left = prefix[i]`
  - `sum_mid = prefix[j] - prefix[i]`
  - `sum_right = prefix[n] - prefix[j]`
- Check if the conditions `sum_left <= sum_mid` and `sum_mid <= sum_right` are satisfied.
- If they are, increment the `count`.
- After the loops complete, return `count` modulo `10^9 + 7`.

## Iterate First Split and Binary Search Second
This approach improves upon the brute-force method by optimizing the search for the second split point `j`. After fixing the first split point `i`, the conditions on the sums of the subarrays translate into a range requirement for the value of `prefix[j]`. Since the prefix sum array is monotonically non-decreasing, we can efficiently find the number of valid `j`'s that fall into this range using binary search. For each `i`, we perform two binary searches: one to find the minimum valid `j` and another to find the maximum valid `j`. This reduces the complexity of the inner loop from O(n) to O(log n).
**Time:** O(n log n). The main loop runs O(n) times, and each iteration involves two binary searches, each taking O(log n) time. · **Space:** O(n) to store the prefix sum array. (Can be O(1) if we modify the input array to be a prefix sum array).
**Pros:** Significantly more efficient than the brute-force approach.; Efficient enough to pass the time limits for the given constraints.
**Cons:** Slightly more complex to implement due to the binary search logic.; Not the most optimal solution, although it passes the time limits.
### Explanation
For a fixed first split point `i`, we need to find the number of valid second split points `j`. The conditions are `sum(left) <= sum(mid)` and `sum(mid) <= sum(right)`. Using the prefix sum array `prefix`, these inequalities become `prefix[i] <= prefix[j] - prefix[i]` and `prefix[j] - prefix[i] <= prefix[n] - prefix[j]`. Rearranging them, we get a condition on `prefix[j]`: `2 * prefix[i] <= prefix[j] <= (prefix[n] + prefix[i]) / 2`.

Our goal is to count how many indices `j` (where `i+1 <= j < n`) satisfy this. Since `nums` has non-negative integers, `prefix` is a sorted (non-decreasing) array. This structure is perfect for binary search.

For each `i`, we find:
1. `j_min`: The first index `j` in `[i+1, n-1]` such that `prefix[j]` is at least `2 * prefix[i]`. This can be found using a lower-bound binary search.
2. `j_max`: The last index `j` in `[i+1, n-1]` such that `prefix[j]` is at most `(prefix[n] + prefix[i]) / 2`. This can be found using an upper-bound binary search.

If `j_min` and `j_max` exist and `j_min <= j_max`, then any `j` in the range `[j_min, j_max]` is a valid second split point. The number of such points is `j_max - j_min + 1`. We sum these counts for all `i` to get the final answer.

```java
class Solution {
    public int waysToSplit(int[] nums) {
        int n = nums.length;
        int MOD = 1_000_000_007;
        int[] prefix = new int[n];
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        long count = 0;
        // i is the index of the last element of the left part
        for (int i = 0; i < n - 2; i++) {
            int sum_left = prefix[i];

            // Find the minimum valid j (start of mid part)
            int j_min_idx = lower_bound(prefix, 2 * sum_left, i + 1, n - 2);
            if (j_min_idx == -1) continue; // No valid j found

            // Find the maximum valid j (start of mid part)
            int j_max_idx = upper_bound(prefix, (prefix[n - 1] + sum_left) / 2, j_min_idx, n - 2);
            if (j_max_idx == -1) continue; // No valid j found

            count = (count + (j_max_idx - j_min_idx + 1)) % MOD;
        }

        return (int) count;
    }

    // Finds the first index k >= startIdx where prefix[k] >= target
    private int lower_bound(int[] prefix, int target, int startIdx, int endIdx) {
        int low = startIdx, high = endIdx, ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (prefix[mid] >= target) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    // Finds the last index k <= endIdx where prefix[k] <= target
    private int upper_bound(int[] prefix, int target, int startIdx, int endIdx) {
        int low = startIdx, high = endIdx, ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (prefix[mid] <= target) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }
}
// Note: The split points in this code are 0-indexed (i and j), 
// representing the end of left and mid subarrays respectively.
// left: [0...i], mid: [i+1...j], right: [j+1...n-1]
```
### Algorithm
- First, compute the prefix sum array `prefix` for `nums`.
- Initialize `count = 0`.
- Iterate with the first split point `i` from `1` to `n-2`.
- For each `i`, we need to find the number of valid second split points `j` (`i+1 <= j < n`) that satisfy the conditions:
  - `sum(left) <= sum(mid)` => `prefix[i] <= prefix[j] - prefix[i]` => `2 * prefix[i] <= prefix[j]`
  - `sum(mid) <= sum(right)` => `prefix[j] - prefix[i] <= prefix[n] - prefix[j]` => `prefix[j] <= (prefix[n] + prefix[i]) / 2`
- This means for a fixed `i`, we are looking for `j` in the range `[i+1, n-1]` such that `2 * prefix[i] <= prefix[j] <= (prefix[n] + prefix[i]) / 2`.
- Since `nums` contains non-negative numbers, the `prefix` array is non-decreasing. We can use binary search to find the valid range for `j`.
- Use a binary search (lower bound) to find the smallest index `j_min` in `[i+1, n-1]` where `prefix[j_min] >= 2 * prefix[i]`.
- Use another binary search (upper bound) to find the largest index `j_max` in `[i+1, n-1]` where `prefix[j_max] <= (prefix[n] + prefix[i]) / 2`.
- If valid `j_min` and `j_max` are found and `j_min <= j_max`, the number of valid splits for the current `i` is `j_max - j_min + 1`. Add this to the total `count`.
- Return the total `count` modulo `10^9 + 7`.

## Two Pointers / Sliding Window
This is the most optimal approach, building upon the insights from the binary search solution. We iterate through the first split point `i` and need to find the valid range for the second split point. We observe that as `i` increases, the lower and upper bounds for the second split point `j` also move monotonically to the right. This allows us to use a two-pointer (or sliding window) technique. We maintain two pointers, `j` and `k`, that track the start and end of the valid range for the second split. As we increment `i`, we simply slide `j` and `k` forward from their previous positions to find the new valid range. This avoids the repeated O(log n) work of binary search in each iteration, bringing the amortized time for finding the range down to O(1).
**Time:** O(n). The main loop for `i` runs O(n) times. The two pointers `j` and `k` only move forward, and each will traverse the array at most once across all iterations of the outer loop. Thus, the work inside the loop is amortized to O(1). · **Space:** O(n) for the prefix sum array. This can be optimized to O(1) by modifying the input array in-place to store prefix sums.
**Pros:** Most efficient solution with linear time complexity.; Optimal for the given constraints.
**Cons:** The logic with three pointers (`i`, `j`, `k`) can be slightly tricky to get right initially.
### Explanation
The key observation is the monotonic relationship between the first split point `i` and the valid range for the second split point. Let's fix the first split point after index `i-1`. We need to find the range of the second split point `j` (from `i+1` to `n-1`) that satisfies the two sum conditions.

Let `j_min` be the first valid index for the second split and `k_max` be the last valid index. As `i` increases, `sum(left)` increases. To maintain `sum(left) <= sum(mid)`, `sum(mid)` must also increase, which means `j_min` must increase or stay the same. Similarly, to maintain `sum(mid) <= sum(right)`, `k_max` must also increase or stay the same. Both `j_min` and `k_max` are non-decreasing with `i`.

This allows us to use two pointers, let's call them `j` and `k`, to track the boundaries. We iterate `i` from `1` to `n-2`. For each `i`, we update `j` and `k`:
- `j` is our lower bound pointer. We advance `j` from its last position until `sum(left) <= sum(mid)`. `j` should always be at least `i+1`.
- `k` is our upper bound pointer. We advance `k` from its last position as long as `sum(mid) <= sum(right)`.

The number of valid splits for the current `i` is then `k - j`. We sum this up for all `i`.
Since each of the three pointers (`i`, `j`, `k`) traverses the array at most once, the total time complexity is linear.

```java
class Solution {
    public int waysToSplit(int[] nums) {
        int n = nums.length;
        int MOD = 1_000_000_007;
        int[] prefix = new int[n];
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        long count = 0;
        int j = 0, k = 0;

        // i is the index of the first split point (end of left part)
        for (int i = 0; i < n - 2; i++) {
            int sum_left = prefix[i];

            // Find the first valid j (start of mid part)
            // j must be at least i + 1
            j = Math.max(j, i + 1);
            while (j < n - 1 && prefix[j] - sum_left < sum_left) {
                j++;
            }

            // Find the first invalid k (end of mid part)
            // k must be at least j
            k = Math.max(k, j);
            while (k < n - 1 && prefix[k] - sum_left <= prefix[n - 1] - prefix[k]) {
                k++;
            }

            // All indices from j to k-1 are valid for the second split
            if (j < n - 1 && k > j) {
                count = (count + (k - j)) % MOD;
            }
        }

        return (int) count;
    }
}
// Note: The split points in this code are 0-indexed (i, j, k),
// representing the end of left, start of mid, and end of mid subarrays.
// left: [0...i], mid: [i+1...j/k], right: [j/k+1...n-1]
```
### Algorithm
- Compute the prefix sum array `prefix`.
- Initialize `count = 0`, and two pointers `j` and `k` (representing the start and end of the valid range for the second split) to `i+1`.
- Iterate with the first split point `i` from `1` to `n-2`.
- For each `i`, we need to find the range of valid second split points. Instead of using binary search, we advance our pointers `j` and `k`.
- **Advance pointer `j`**: This pointer finds the lower bound for the second split. Move `j` forward as long as `sum(left) > sum(mid)`. The condition is `prefix[i] > prefix[j] - prefix[i]`. We advance `j` until this is no longer true. Since `i` increases, `sum(left)` increases, so `j` will only ever move forward.
- **Advance pointer `k`**: This pointer finds the upper bound. Move `k` forward as long as `sum(mid) <= sum(right)`. The condition is `prefix[k] - prefix[i] <= prefix[n] - prefix[k]`. We advance `k` until this is no longer true. The valid indices for the second split are up to `k-1`.
- The number of valid splits for the current `i` is the size of the range `[j, k-1]`, which is `k - j`.
- Add `k - j` to the total `count` (if `k > j`).
- Ensure pointers `j` and `k` always start at least at `i+1`.
- Return the total `count` modulo `10^9 + 7`.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int waysToSplit(int[] nums) {
    int n = nums.length;
    int[] s = new int[n];
    s[0] = nums[0];
    for (int i = 1; i < n; ++i) {
      s[i] = s[i - 1] + nums[i];
    }
    int ans = 0;
    for (int i = 0; i < n - 2; ++i) {
      int j = search(s, s[i] << 1, i + 1, n - 1);
      int k = search(s, ((s[n - 1] + s[i]) >> 1) + 1, j, n - 1);
      ans = (ans + k - j) % MOD;
    }
    return ans;
  }
private
  int search(int[] s, int x, int left, int right) {
    while (left < right) {
      int mid = (left + right) >> 1;
      if (s[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var waysToSplit = function ( nums ) { const mod = 1 e9 + 7 ; const n = nums . length ; const s = new Array ( n ). fill ( nums [ 0 ]); for ( let i = 1 ; i < n ; ++ i ) { s [ i ] = s [ i - 1 ] + nums [ i ]; } function search ( s , x , left , right ) { while ( left < right ) { const mid = ( left + right ) >> 1 ; if ( s [ mid ] >= x ) { right = mid ; } else { left = mid + 1 ; } } return left ; } let ans = 0 ; for ( let i = 0 ; i < n - 2 ; ++ i ) { const j = search ( s , s [ i ] << 1 , i + 1 , n - 1 ); const k = search ( s , (( s [ n - 1 ] + s [ i ]) >> 1 ) + 1 , j , n - 1 ); ans = ( ans + k - j ) % mod ; } return ans ; };

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int waysToSplit(vector<int> &nums) {
    int n = nums.size();
    vector<int> s(n, nums[0]);
    for (int i = 1; i < n; ++i)
      s[i] = s[i - 1] + nums[i];
    int ans = 0;
    for (int i = 0; i < n - 2; ++i) {
      int j = lower_bound(s.begin() + i + 1, s.begin() + n - 1, s[i] << 1) -
              s.begin();
      int k = upper_bound(s.begin() + j, s.begin() + n - 1,
                          (s[n - 1] + s[i]) >> 1) -
              s.begin();
      ans = (ans + k - j) % mod;
    }
    return ans;
  }
};

```

### Python

```python
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) k = bisect_right(s, (s[- 1] + s[i]) >> 1, j, n - 1) ans += k - j return ans % mod

```