Ways to Split Array Into Three Subarrays

Medium
1351.

Ways to Split Array Into Three Subarrays

Ways to Split Array Into Three Subarrays is a medium coding problem on arrays, binary search and two pointers, asked in Amazon and Google interviews.

You are given an array nums of non-negative integers. Cut it into three non-empty contiguous parts — left, mid and right, in that order — so that every element belongs to exactly one part.

A cut is good when sum(left) <= sum(mid) <= sum(right).

Return the number of good cuts. Two cuts are different when at least one of the two cut positions differs. Since the count can be huge, return it modulo 10^9 + 7.

Example 1

Input
nums = [2,2,2]
Output
1
Explanation
The only cut is `[2] | [2] | [2]`, and 2 <= 2 <= 2.

Example 2

Input
nums = [1,3,1,2,4,1]
Output
2
Explanation
`[1] | [3] | [1,2,4,1]` and `[1] | [3,1] | [2,4,1]`.

Example 3

Input
nums = [5,1,1]
Output
0
Explanation
The left part alone already outweighs the middle.

Constraints

  • 3 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var waysToSplit = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Ways to Split Array Into Three Subarrays — Solution

Ways to Split Array Into Three Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Ways to Split Array Into Three Subarrays is a medium coding problem on arrays, binary search and two pointers, asked in Amazon and Google interviews.

Problem statement

You are given an array nums of non-negative integers. Cut it into three non-empty contiguous parts — left, mid and right, in that order — so that every element belongs to exactly one part.

A cut is good when sum(left) <= sum(mid) <= sum(right).

Return the number of good cuts. Two cuts are different when at least one of the two cut positions differs. Since the count can be huge, return it modulo 10^9 + 7.

Example 1

Input: nums = [2,2,2]
Output: 1
Explanation: The only cut is `[2] | [2] | [2]`, and 2 <= 2 <= 2.

Example 2

Input: nums = [1,3,1,2,4,1]
Output: 2
Explanation: `[1] | [3] | [1,2,4,1]` and `[1] | [3,1] | [2,4,1]`.

Example 3

Input: nums = [5,1,1]
Output: 0
Explanation: The left part alone already outweighs the middle.

Constraints

  • 3 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^4

Hints for Ways to Split Array Into Three Subarrays

  1. Hint 1

    With prefix sums P, a cut after i elements and after j elements gives sums P[i], P[j] - P[i] and P[n] - P[j].

  2. Hint 2

    For a fixed i the conditions become P[j] >= 2 * P[i] and 2 * P[j] <= P[n] + P[i]. Because the numbers are non-negative, P never decreases, so the valid j form one contiguous range.

  3. Hint 3

    Both ends of that range only move right as i grows, so two pointers (or two binary searches per i) count every range in total linear time. Stop once 3 * P[i] > P[n].

How to solve Ways to Split Array Into Three Subarrays

Fix the end of the left part. Because every element is non-negative, prefix sums are non-decreasing, so the valid end positions of the middle part form a contiguous range whose two boundaries never move left as the left part grows.

Approach

  1. Build prefix sums P with P[0] = 0 and P[k] = sum of the first k elements; let total = P[n].
  2. For i from 1 to n - 2 (left = first i elements): if 3 * P[i] > total, stop — no later i can work.
  3. Advance j (starting at least at i + 1) while j <= n - 1 and P[j] < 2 * P[i]; j is the first valid middle end.
  4. Advance k (starting at least at j) while k <= n - 1 and 2 * P[k] <= total + P[i]; k is one past the last valid middle end.
  5. Add k - j to the answer, modulo 10^9 + 7.

Why it works

P[j] >= 2P[i] is sum(mid) >= sum(left) and 2P[j] <= total + P[i] is sum(right) >= sum(mid). Since P is non-decreasing, the first condition holds on a suffix of positions and the second on a prefix, so their intersection is a range [j, k). Increasing i raises both thresholds, so both j and k only move forward — every pointer travels at most n steps.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • 2 * P[i], 3 * P[i] and total + P[i] reach about 3·10^9 — use 64-bit arithmetic in fixed-width languages.
  • The middle and right parts must be non-empty: j ranges over i + 1 .. n - 1, never n.
  • Zeros make many cuts valid at once (an all-zero array of length n has (n-1)(n-2)/2 good cuts), so the count needs the modulus.

Reference solution

Python

from typing import List

def waysToSplit(nums: List[int]) -> int:
    MOD = 10 ** 9 + 7
    n = len(nums)
    pre = [0] * (n + 1)
    for i, v in enumerate(nums):
        pre[i + 1] = pre[i] + v
    total = pre[n]
    ans = 0
    j = 0
    k = 0
    for i in range(1, n - 1):
        if 3 * pre[i] > total:
            break
        j = max(j, i + 1)
        while j <= n - 1 and pre[j] < 2 * pre[i]:
            j += 1
        k = max(k, j)
        while k <= n - 1 and 2 * pre[k] <= total + pre[i]:
            k += 1
        ans += k - j
    return ans % MOD

Java

public static int waysToSplit(int[] nums) {
    final long MOD = 1000000007L;
    int n = nums.length;
    long[] pre = new long[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
    long total = pre[n];
    long ans = 0;
    int j = 0, k = 0;
    for (int i = 1; i <= n - 2; i++) {
        if (3 * pre[i] > total) break;
        if (j < i + 1) j = i + 1;
        while (j <= n - 1 && pre[j] < 2 * pre[i]) j++;
        if (k < j) k = j;
        while (k <= n - 1 && 2 * pre[k] <= total + pre[i]) k++;
        ans = (ans + k - j) % MOD;
    }
    return (int) ans;
}

C++

int waysToSplit(vector<int>& nums) {
    const long long MOD = 1000000007LL;
    int n = nums.size();
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
    long long total = pre[n];
    long long ans = 0;
    int j = 0, k = 0;
    for (int i = 1; i <= n - 2; i++) {
        if (3 * pre[i] > total) break;
        if (j < i + 1) j = i + 1;
        while (j <= n - 1 && pre[j] < 2 * pre[i]) j++;
        if (k < j) k = j;
        while (k <= n - 1 && 2 * pre[k] <= total + pre[i]) k++;
        ans = (ans + k - j) % MOD;
    }
    return (int) ans;
}

JavaScript

var waysToSplit = function(nums) {
    var MOD = 1000000007;
    var n = nums.length;
    var pre = new Array(n + 1);
    pre[0] = 0;
    for (var i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
    var total = pre[n];
    var ans = 0, j = 0, k = 0;
    for (var i = 1; i <= n - 2; i++) {
        if (3 * pre[i] > total) break;
        if (j < i + 1) j = i + 1;
        while (j <= n - 1 && pre[j] < 2 * pre[i]) j++;
        if (k < j) k = j;
        while (k <= n - 1 && 2 * pre[k] <= total + pre[i]) k++;
        ans = (ans + k - j) % MOD;
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search