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:
- The sum of the first
i + 1
elements is greater than or equal to the sum of the lastn - i - 1
elements. - 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:
- Precompute the total sum of the array.
- Use a prefix sum to keep track of the sum of the first part as we iterate through the array.
- 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
- Compute Total Sum:
- Calculate the total sum of the array
nums
.
- Calculate the total sum of the array
- 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 astotalSum - prefixSum
. - If
prefixSum >= remainingSum
, increment the count of valid splits.
- 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.
Leetcode Related Problems
- ๐ข - 1991. Find the Middle Index in Array
- ๐ข - 0724. Find Pivot Index
- ๐ด - 2035. Partition Array Into Two Arrays to Minimize Sum Difference
- ๐ด - 0410. Split Array Largest Sum
- ๐ก - 1712. Ways to Split Array Into Three Subarrays
- ๐ก - 2256. Minimum Average Difference
GeeksForGeeks Related Problems
- ๐ก - Prefix Sum Array
- ๐ก - Equilibrium Index of an Array
LintCode Related Problems
- ๐ก - 943. Range Sum Query - Immutable
- ๐ - 944. Maximum Submatrix