Number of Ways to Split Array — Problem & Solution
Number of Ways to Split Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Ways to Split Array is a medium coding problem on arrays and prefix sum, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Prefix Sum
- Asked at: Amazon, Microsoft
- 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
A split of the integer array nums (length n) at index i, where 0 <= i < n - 1, cuts it into a left part nums[0..i] and a right part nums[i+1..n-1]. Both parts are therefore non-empty.
The split is valid when the sum of the left part is greater than or equal to the sum of the right part.
Return the number of valid splits.
Example 1
Input: nums = [4,-2,6,-3]
Output: 2
Explanation: Cutting after index 0 gives 4 vs 1, and after index 2 gives 8 vs -3. Cutting after index 1 gives 2 vs 3, which is not valid.
Example 2
Input: nums = [1,1]
Output: 1
Example 3
Input: nums = [-5,3,3]
Output: 0
Constraints
2 <= nums.length <= 10^5-10^5 <= nums[i] <= 10^5
Hints for Number of Ways to Split Array
Hint 1
Summing both sides from scratch for every cut is quadratic.
Hint 2
If you know the total, the right part's sum is
total - left.Hint 3
Sweep once with a running left sum (64-bit: it can reach
10^10in magnitude) and stop before the last index.
How to solve Number of Ways to Split Array
The right part's sum is always the total minus the left part's sum, so a single prefix sweep checks every cut in O(1).
Approach
- Compute
total, the sum of the whole array, in a 64-bit integer. - Sweep
ifrom 0 ton - 2, addingnums[i]toleft. - Count the cut when
left >= total - left. - Return the count.
Why it works
At cut i the left part is exactly the prefix nums[0..i] and the right part is everything else, whose sum is total - left. Every legal cut is visited once, and the last index is excluded because the right part must be non-empty.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The loop stops at
n - 2; cutting after the last element leaves the right side empty. - Negative numbers mean the left sum is not monotonic — do not stop early or binary search.
- Sums reach
10^10in magnitude, beyond 32-bit range.
Reference solution
Python
from typing import List
def waysToSplitArray(nums: List[int]) -> int:
total = sum(nums)
left = 0
ways = 0
for i in range(len(nums) - 1):
left += nums[i]
if left >= total - left:
ways += 1
return waysJava
public static int waysToSplitArray(int[] nums) {
long total = 0;
for (int x : nums) total += x;
long left = 0;
int ways = 0;
for (int i = 0; i < nums.length - 1; i++) {
left += nums[i];
if (left >= total - left) ways++;
}
return ways;
}C++
int waysToSplitArray(vector<int>& nums) {
long long total = 0;
for (int x : nums) total += x;
long long left = 0;
int ways = 0;
for (int i = 0; i + 1 < (int)nums.size(); i++) {
left += nums[i];
if (left >= total - left) ways++;
}
return ways;
}JavaScript
var waysToSplitArray = function(nums) {
var total = 0;
for (var i = 0; i < nums.length; i++) total += nums[i];
var left = 0, ways = 0;
for (var j = 0; j < nums.length - 1; j++) {
left += nums[j];
if (left >= total - left) ways++;
}
return ways;
};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 · Prefix Sum