 Number of Ways to Split Array- Two Approaches✅|| Beats 100% 🚀|| Prefix Sum & Single Pass || JAVA ☕
IntuitionThe problem asks us to find the number of valid splits in an array such that the sum of the left part is greater than or equal to the sum of the right
# Intuition
The problem asks us to find the number of valid splits in an array such that the sum of the left part is greater than or equal to the sum of the right part. My initial thought was to maintain prefix sums for both left and right parts of the array, but I later realized that a single pass with cumulative sums can optimize the solution.

# Approach 1: Two-Prefix Arrays
![Screenshot 2025-01-03 085847.png](https://assets.leetcode.com/users/images/fa658436-ee2b-459d-b613-1dbc2cae4de7_1735875719.64038.png)

In the first approach, we use two separate arrays to calculate the prefix sums for both the left and right parts of the array.

# Steps:

1. Compute a leftSum array where each element at index i stores the sum of elements from index 0 to i.

2. Compute a rightSum array where each element at index i stores the sum of elements from index i to the end of the array.

3. Iterate through the array, checking if the left sum at index i is greater than or equal to the right sum at index i+1.

# Complexity
- Time complexity: **O(N)**

- Space complexity: **O(N)**

# Code
```java []
class Solution {
    public int waysToSplitArray(int[] nums) {
        int n = nums.length;
        int count = 0;

        // Initialize leftSum array and set the first element
        long leftSum[] = new long[n];
        leftSum[0] = nums[0];

        // Initialize rightSum array and set the last element
        long rightSum[] = new long[n];
        rightSum[n - 1] = nums[n - 1];

        // Calculate the prefix sums for the left part
        for (int i = 1; i < n; i++) {
            leftSum[i] = leftSum[i - 1] + nums[i];
        }

        // Calculate the prefix sums for the right part
        for (int i = n - 2; i >= 0; i--) {
            rightSum[i] = rightSum[i + 1] + nums[i];
        }

        // Count valid splits where leftSum[i] >= rightSum[i+1]
        for (int i = 0; i < n - 1; i++) {
            if (leftSum[i] >= rightSum[i + 1]) {
                count++;
            }
        }

        return count;
    }
}
```

# Approach 2: Single-Pass with Total Sum
The second approach is more efficient in terms of space usage. Instead of using additional arrays, we calculate the total sum of the array first and then keep a running sum for the left part of the array during a single pass.

![Screenshot 2025-01-03 085905.png](https://assets.leetcode.com/users/images/36a00746-26ec-41c0-a693-bcf47f0e1cf6_1735875741.0051503.png)


# Steps:

1. Calculate the total sum of the array.

2. Use a variable leftSum to accumulate the sum of the left part of the array as you iterate through it.

3. At each step, calculate the right sum by subtracting leftSum from totalSum.

4. If the left sum is greater than or equal to the right sum, increment the count.


# Code
```java []
class Solution {
    public int waysToSplitArray(int[] nums) {
        int n = nums.length;
        long totalSum = 0;
        long leftSum = 0;
        int count = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totalSum += nums[i];
        }

        // Iterate through the array to count valid splits
        for (int i = 0; i < n - 1; i++) {
            leftSum += nums[i];
            long rightSum = totalSum - leftSum;

            // Check if the left sum is greater than or equal to the right sum
            if (leftSum >= rightSum) {
                count++;
            }
        }

        return count;
    }
}
```

# Complexity
- Time complexity: **O(N)**

- Space complexity: **O(1)**

# ⬆️⬆️⬆️⬆️⬆️⬆️⬆️UPVOTE ⬆️⬆️⬆️⬆️⬆️⬆ 

['Java']