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.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Two Pointers, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^50 <= nums[i] <= 10^4
Hints for Ways to Split Array Into Three Subarrays
Hint 1
With prefix sums
P, a cut afterielements and afterjelements gives sumsP[i],P[j] - P[i]andP[n] - P[j].Hint 2
For a fixed
ithe conditions becomeP[j] >= 2 * P[i]and2 * P[j] <= P[n] + P[i]. Because the numbers are non-negative,Pnever decreases, so the validjform one contiguous range.Hint 3
Both ends of that range only move right as
igrows, so two pointers (or two binary searches peri) count every range in total linear time. Stop once3 * 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
- Build prefix sums
PwithP[0] = 0andP[k]= sum of the firstkelements; lettotal = P[n]. - For
ifrom 1 ton - 2(left = firstielements): if3 * P[i] > total, stop — no laterican work. - Advance
j(starting at least ati + 1) whilej <= n - 1andP[j] < 2 * P[i];jis the first valid middle end. - Advance
k(starting at least atj) whilek <= n - 1and2 * P[k] <= total + P[i];kis one past the last valid middle end. - Add
k - jto the answer, modulo10^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]andtotal + P[i]reach about 3·10^9 — use 64-bit arithmetic in fixed-width languages.- The middle and right parts must be non-empty:
jranges overi + 1 .. n - 1, nevern. - Zeros make many cuts valid at once (an all-zero array of length
nhas(n-1)(n-2)/2good 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 % MODJava
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