Number of Ways to Split Array

MEDIUM

Description

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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵

Approaches

Checkout 2 different approaches to solve Number of Ways to Split Array. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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.

Complexity Analysis

Time Complexity: 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 Complexity: O(1). We only use a few variables to store the sums and the count, which does not depend on the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Number of Ways to Split Array. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Number of Ways to Split Array

Patterns:

Prefix Sum

Data Structures:

Array