2256. Number of Ways to Split Array

ยท
3 min read
Difficulty: Medium

Problem Description

Given a 0-indexed integer array nums of length n, a valid split at index i occurs if:

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

Return the number of valid splits in nums.

Example:

Input: nums = [10,4,-8,7]
Output: 2
Explanation: 
- Split at index 0: [10] and [4,-8,7]. Sums are 10 and 3. Valid.
- Split at index 1: [10,4] and [-8,7]. Sums are 14 and -1. Valid.
- Split at index 2: [10,4,-8] and [7]. Sums are 6 and 7. Invalid.
Thus, there are 2 valid splits.

Solution Code

class Solution {
    public int waysToSplitArray(int[] nums) {
        int n = nums.length;
        long totalSum = 0; // Use long to avoid integer overflow
        for (int num : nums) {
            totalSum += num;
        }
        
        int validSplits = 0;
        long prefixSum = 0; // Use long to avoid integer overflow
        
        for (int i = 0; i < n - 1; i++) {
            prefixSum += nums[i];
            long remainingSum = totalSum - prefixSum;
            if (prefixSum >= remainingSum) {
                validSplits++;
            }
        }
        
        return validSplits;
    }
}

Approach Name

Prefix Sum Approach

Intuition

The problem requires us to count the number of valid splits in the array. A split is valid if the sum of the first part is greater than or equal to the sum of the second part. To efficiently compute the sums for all possible splits, we can:

  1. Precompute the total sum of the array.
  2. Use a prefix sum to keep track of the sum of the first part as we iterate through the array.
  3. For each index, calculate the remaining sum (total sum - prefix sum) and check if the prefix sum is greater than or equal to the remaining sum.

Algorithm

  1. Compute Total Sum:
    • Calculate the total sum of the array nums.
  2. Iterate Through Array:
    • Use a prefix sum to accumulate the sum of the first part as we iterate through the array.
    • For each index i, calculate the remaining sum as totalSum - prefixSum.
    • If prefixSum >= remainingSum, increment the count of valid splits.
  3. Return Result:
    • Return the count of valid splits.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We traverse the array twice: once to compute the total sum and once to compute the prefix sums and check for valid splits.
  • Space Complexity: O(1), as we are using only a few extra variables for computation.
  1. ๐ŸŸข - 1991. Find the Middle Index in Array
  2. ๐ŸŸข - 0724. Find Pivot Index
  3. ๐Ÿ”ด - 2035. Partition Array Into Two Arrays to Minimize Sum Difference
  4. ๐Ÿ”ด - 0410. Split Array Largest Sum
  5. ๐ŸŸก - 1712. Ways to Split Array Into Three Subarrays
  6. ๐ŸŸก - 2256. Minimum Average Difference
  1. ๐ŸŸก - Prefix Sum Array
  2. ๐ŸŸก - Equilibrium Index of an Array
  1. ๐ŸŸก - 943. Range Sum Query - Immutable
  2. ๐Ÿ”’ - 944. Maximum Submatrix