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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6

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

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

We can iterate for all possible split points and compute the sum on the left and right sides for each split, the naive approach would involve time complexity of O(n^2) as we check for n-1 split points and calculate the sum for each split point which takes O(n) time, resulting in overall time complexity of O(n^2).

Method 2 - Using Prefix Sum

The problem requires identifying valid splits in the array where the sum of the subarray on the left (up to and including index i) is greater than or equal to the sum on the right (from index i+1 onwards).

To solve the problem efficiently, follow these steps:

  1. Initial Setup: Calculate the total sum of the array, which represents the sum of the right side when no elements are included on the left side initially.
  2. Iterate through Possible Splits:
    • Use a loop to traverse the array, stopping before the last element (since we need at least one element on the right side for a split).
    • For each index:
      • Increment the left side sum by adding the current element.
      • Update the right side sum by subtracting the current element from the total sum.
      • Check whether the left side sum is greater than or equal to the right side sum. If this condition is met, increment the count of valid splits.
  3. Return Result: After completing the iteration, return the count of valid splits identified.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int waysToSplitArray(int[] nums) {
        long totalSum = 0;
        
        // Calculate the total sum of the array
        for (int num : nums) {
            totalSum += num;
        }

        long leftSum = 0, rightSum = totalSum;
        int validSplits = 0;
        // Iterate to find valid splits
        for (int i = 0; i < nums.length - 1; i++) {
            leftSum += nums[i];
            rightSum -= nums[i];
            if (leftSum >= rightSum) {
                validSplits++;
            }
        }

        return validSplits;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        total_sum: int = sum(nums)
        left_sum: int = 0
        right_sum: int = total_sum
        valid_splits: int = 0
        
        # Iterate to find valid splits
        for i in range(len(nums) - 1):
            left_sum += nums[i]
            right_sum -= nums[i]
            if left_sum >= right_sum:
                valid_splits += 1

        return valid_splits

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the nums array, as we traverse the array once to compute the total sum and again to find the valid splits.
  • 🧺 Space complexity: O(1) as we use a few extra variables for sums and counts, but no additional space proportional to input size.