C++ | Prefix Sum | Number of Ways to Split Array | O(n) Time, O(1) Space
IntuitionThe problem involves finding the number of valid splits in an array where the sum of the left part is greater than or equal to the sum of the right par
# Intuition
The problem involves finding the number of valid splits in an array where the sum of the left part is greater than or equal to the sum of the right part. A brute-force approach would involve calculating sums for every split, which is inefficient. Instead, we use the **prefix sum** technique to optimize the solution.

# Approach

### Normal Prefix Sum Approach:
1. Compute a `prefixSum` array where `prefixSum[i]` represents the sum of the first \(i+1\) elements of `nums`.
2. The total sum of the array is stored in `prefixSum[n-1]`.
3. For each index \(i\) from 0 to \(n-2\), check if the sum of the left part (`prefixSum[i]`) is greater than or equal to the sum of the right part (`prefixSum[n-1] - prefixSum[i]`).
4. Count the indices where the condition is satisfied.

### Space-Optimized Approach:
1. Instead of maintaining a `prefixSum` array, use a variable `prefixSum` to calculate the left sum on the fly.
2. Compute the total sum of the array (`totalSum`).
3. For each index \(i\), dynamically update `prefixSum` and check the same condition as in the normal approach.

# Complexity
- **Time complexity**:  
  - Computing prefix sums takes $$O(n)$$.
  - Checking valid splits also takes $$O(n)$$.  
  - Overall: $$O(n)$$.

- **Space complexity**:  
  - **Normal Prefix Sum Approach**: $$O(n)$$ due to the `prefixSum` array.  
  - **Space-Optimized Approach**: $$O(1)$$ since it uses only variables for calculations.

# Code

### Normal Prefix Sum Approach
```cpp
class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        int n = nums.size();
        vector<long long> prefixSum(n, 0); // Use long long for prefixSum to avoid overflow

        // Compute prefix sums
        prefixSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }

        int cnt = 0;

        // Check valid splits
        for (int i = 0; i < n - 1; i++) {
            if (prefixSum[i] >= (prefixSum[n - 1] - prefixSum[i])) {
                cnt++;
            }
        }

        return cnt;
    }
};
```

### Space-Optimized Approach
```cpp
class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        int n = nums.size();
        long long totalSum = 0, prefixSum = 0;

        // Compute total sum of the array
        for (int num : nums) {
            totalSum += num;
        }

        int cnt = 0;

        // Dynamically compute prefix sum and check valid splits
        for (int i = 0; i < n - 1; i++) {
            prefixSum += nums[i];
            if (prefixSum >= (totalSum - prefixSum)) {
                cnt++;
            }
        }

        return cnt;
    }
};

['Array', 'Prefix Sum', 'C++']