Number of Ways to Split Array

How it works

We don't need to store the entire prefix sum array. Instead, we can maintain a running left sum and right sum. Start with right as the total, then shift elements from right to left as we iterate through possible split points.

Steps

1. Compute the total sum and assign it to right.
2. Initialize left = 0 and res = 0.
3. For each index i from 0 to n - 2:
   • Add nums[i] to left and subtract it from right.
   • If left >= right, increment res.
4. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Off-by-One Error in Loop Bounds

The split must have at least one element on each side, so valid split indices are from 0 to n-2 (inclusive). A common mistake is iterating up to n-1, which would leave the right side empty. Always ensure the loop condition is i < n - 1 or equivalent.

Integer Overflow with Large Sums

The array can contain values up to 10^9 and have up to 10^5 elements, so the total sum can exceed the 32-bit integer range. Using int for sums in Java, C++, or similar languages causes overflow and incorrect comparisons. Always use long or long long for the sum variables.

Comparing Sums Before Updating Them

In the optimal one-pass approach, the order of operations matters. You must first add nums[i] to left and subtract from right, then compare. A common bug is comparing before updating, which checks the wrong split point. The correct sequence is: update sums, then check if left >= right.

from typing import List

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        right = sum(nums)
        left = res = 0

        for i in range(len(nums) - 1):
            left += nums[i]
            right -= nums[i]
            res += 1 if left >= right else 0

        return res

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        long long right = 0, left = 0;
        for (int num : nums) {
            right += num;
        }

        int res = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            left += nums[i];
            right -= nums[i];
            if (left >= right) {
                res++;
            }
        }

        return res;
    }
};