Efficient Array Splitting With O(n) Prefix Sum Calculation
Calculating prefix sum in O(n) time, then iterating over it to find valid splits also in O(n). Solution returns count of ways to split array.
Problem
TC: O(n) for calculating prefix sum, and O(n) for iterating over the prefix sum for calculating valid splits
class Solution {
public int waysToSplitArray(int[] nums) {
long prefix[] = new long[nums.length];
long current = 0;
for(int i=0;i<nums.length;i++){
current+=nums[i];
prefix[i] = current;
}
int count =0;
for(int i =0;i<nums.length-1;i++){
long left = prefix[i];
long right = prefix[nums.length-1];
if(left>=right-left) count++;
}
return count;
}
}...