# Number of Ways to Split Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-ways-to-split-array)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-split-array
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** integer array `nums` of length `n`.

`nums` contains a **valid split** at index `i` if the following are true:

* The sum of the first `i + 1` elements is **greater than or equal to** the sum of the last `n - i - 1` elements.
* There is **at least one** element to the right of `i`. That is, `0 <= i < n - 1`.

Return _the number of **valid splits** in_ `nums`.

**Example 1:**

**Input:** nums = [10,4,-8,7]
**Output:** 2
**Explanation:** 
There are three ways of splitting nums into two non-empty parts:
- Split nums at index 0. Then, the first part is [10], and its sum is 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split.
- Split nums at index 1. Then, the first part is [10,4], and its sum is 14. The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 is a valid split.
- Split nums at index 2. Then, the first part is [10,4,-8], and its sum is 6. The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is not a valid split.
Thus, the number of valid splits in nums is 2.

**Example 2:**

**Input:** nums = [2,3,1,0]
**Output:** 2
**Explanation:** 
There are two valid splits in nums:
- Split nums at index 1. Then, the first part is [2,3], and its sum is 5. The second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split. 
- Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6. The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.

**Constraints:**

* `2 <= nums.length <= 105`
* `-105 <= nums[i] <= 105`

# Approaches
## Brute Force with Nested Loops
This approach directly translates the problem description into code. We iterate through all possible split points and, for each point, we calculate the sum of the left and right subarrays independently using nested loops. We then compare these sums to check if the split is valid.
**Time:** O(n^2), where n is the number of elements in `nums`. The outer loop runs `n-1` times. Inside the loop, calculating the left and right sums takes `O(n)` time in total. This results in a quadratic time complexity, which is too slow for the given constraints. · **Space:** O(1). We only use a few variables to store the sums and the count, which does not depend on the input size.
**Pros:** Simple to understand and implement as it directly follows the problem statement.
**Cons:** Highly inefficient due to redundant calculations.; Will result in a 'Time Limit Exceeded' (TLE) error for large input arrays.
### Explanation
The core idea is to check every possible split index `i` from `0` to `n-2`. For each `i`, we need to compute two sums: `leftSum` (sum of elements from index `0` to `i`) and `rightSum` (sum of elements from index `i+1` to `n-1`).
We can use two separate loops to calculate these sums. After computing both sums, we check if `leftSum >= rightSum`. If this condition holds, we increment a counter for valid splits. This process is repeated for all possible values of `i`.
```java
class Solution {
    public int waysToSplitArray(int[] nums) {
        int n = nums.length;
        int validSplits = 0;
        
        // Iterate through all possible split points
        for (int i = 0; i < n - 1; i++) {
            // Use long to prevent integer overflow
            long leftSum = 0;
            for (int j = 0; j <= i; j++) {
                leftSum += nums[j];
            }
            
            long rightSum = 0;
            for (int k = i + 1; k < n; k++) {
                rightSum += nums[k];
            }
            
            if (leftSum >= rightSum) {
                validSplits++;
            }
        }
        
        return validSplits;
    }
}
```
Note the use of `long` for the sums to avoid potential integer overflow, as the sum of elements can exceed the capacity of a standard 32-bit integer.
### Algorithm
- Initialize a counter `validSplits` to 0.
- Iterate through each possible split index `i` from `0` to `n-2`, where `n` is the length of the array.
- For each `i`, calculate `leftSum`, the sum of elements from `nums[0]` to `nums[i]`.
- For the same `i`, calculate `rightSum`, the sum of elements from `nums[i+1]` to `nums[n-1]`.
- If `leftSum` is greater than or equal to `rightSum`, increment `validSplits`.
- After the loop finishes, return `validSplits`.

## Single Pass with Prefix Sum
A more efficient approach avoids recalculating sums from scratch. We can pre-calculate the total sum of the array. Then, we can iterate through the array once, maintaining a running sum for the left part (`leftSum`). The sum of the right part (`rightSum`) can be found in constant time by subtracting `leftSum` from the `totalSum`.
**Time:** O(n), where n is the number of elements in `nums`. We make two passes through the array: one to calculate the total sum and another to check for valid splits. This is linear time complexity, which is very efficient. · **Space:** O(1). We only use a few variables (`totalSum`, `leftSum`, `validSplits`) to store intermediate values, requiring constant extra space.
**Pros:** Optimal time complexity, solving the problem efficiently within the given constraints.; Space efficient, using only constant extra memory.
**Cons:** Requires careful handling of potential integer overflow by using a larger data type like `long` for sums.
### Explanation
The bottleneck in the brute-force method is the repeated summation. We can optimize this by observing that if we know the `leftSum` and the `totalSum` of the array, the `rightSum` is simply `totalSum - leftSum`.
The algorithm proceeds as follows:
1. First, compute the `totalSum` of all elements in the `nums` array. This requires a single pass. It's crucial to use a `long` data type for the sum to prevent overflow.
2. Initialize a `validSplits` counter to 0 and a `leftSum` to 0.
3. Iterate from `i = 0` to `n-2`. In each step:
    a. Add `nums[i]` to `leftSum`.
    b. Calculate `rightSum` as `totalSum - leftSum`.
    c. Compare `leftSum` and `rightSum`. If `leftSum >= rightSum`, increment `validSplits`.
4. After iterating through all possible split points, return the `validSplits` count.
This approach reduces the time complexity significantly by eliminating the nested loops.
```java
class Solution {
    public int waysToSplitArray(int[] nums) {
        int n = nums.length;
        
        // Use long to prevent integer overflow
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        int validSplits = 0;
        long leftSum = 0;
        
        // Iterate through all possible split points
        for (int i = 0; i < n - 1; i++) {
            // Add current element to the left sum
            leftSum += nums[i];
            
            // Calculate the right sum
            long rightSum = totalSum - leftSum;
            
            // Check the condition for a valid split
            if (leftSum >= rightSum) {
                validSplits++;
            }
        }
        
        return validSplits;
    }
}
```
### Algorithm
- Calculate the `totalSum` of all elements in the array. Use a 64-bit integer (`long`) to avoid overflow.
- Initialize `validSplits = 0` and `leftSum = 0` (as a `long`).
- Iterate with an index `i` from `0` to `n-2`.
- In each iteration, update `leftSum` by adding `nums[i]`.
- Calculate `rightSum` by subtracting the current `leftSum` from `totalSum`.
- If `leftSum >= rightSum`, increment `validSplits`.
- Return `validSplits` after the loop.

# Solutions
### Java

```java
class Solution {
public
  int waysToSplitArray(int[] nums) {
    long s = 0;
    for (int v : nums) {
      s += v;
    }
    int ans = 0;
    long t = 0;
    for (int i = 0; i < nums.length - 1; ++i) {
      t += nums[i];
      if (t >= s - t) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int waysToSplitArray(vector<int> &nums) {
    long long s = accumulate(nums.begin(), nums.end(), 0ll);
    long long t = 0;
    int ans = 0;
    for (int i = 0; i < nums.size() - 1; ++i) {
      t += nums[i];
      ans += t >= s - t;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int: s = sum(nums) ans = t = 0 for v in nums[: - 1]: t += v if t >= s - t: ans += 1 return ans

```