Number of Ways to Split Array

Leetcode Problem:

• Number of Ways to Split Array

Summary

• The problem requires to find the number of valid splits in the given array
• A valid split is when the sum of the first i+1 elements is greater than or equal to the sum of the last n-i-1 elements.

Approach

• The approach used is to calculate the prefix sum of the array and then iterate over the array to check for valid splits
• The prefix sum is calculated using a dynamic programming approach and stored in an array
• Then, for each index i, the sum of the first i+1 elements is compared with the sum of the last n-i-1 elements
• If the sum of the first i+1 elements is greater than or equal to the sum of the last n-i-1 elements, then the index i is considered as a valid split.

Complexity

• O(n)

Explanation

• The time complexity of the solution is O(n) because we are iterating over the array once to calculate the prefix sum and again to check for valid splits
• The space complexity is also O(n) because we are storing the prefix sum in an array of size n.

Solution Code:

class Solution {
public:
    long long pSum[100000];
    int waysToSplitArray(vector& nums) {
        pSum[0] = nums[0];
        for(int i = 1 ; i < nums.size(); i++){
            pSum[i] = pSum[i-1] + nums[i];
        }
        int ans = 0;
        int last = nums.size() - 1;
        for(int i = 0; i < last; i++){
            if(pSum[i] >= pSum[last] - pSum[i]){
                ans++;
            }
        }
        return ans;
    }
};