Beats 100% Easy C++ Using Prefix and Suffix --  Ways to Split Array into Two Parts
Method 1 -- Optimized way of the second method given after thisIntuitionThe task is to split the array into two non-empty parts such that the sum of elements in
# Method 1 -- Optimized way of the second method given after this
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The task is to split the array into two non-empty parts such that the sum of elements in the left part `(lSum)` is greater than or equal to the sum of elements in the right part `(rSum)`. We aim to efficiently calculate the sums on both sides of the split for each potential index while minimizing memory usage.

Instead of recalculating sums repeatedly or precomputing all possible suffix sums, we use two variables (lSum and rSum) to keep track of the cumulative sums dynamically. This allows us to achieve the goal in a single pass with O(1) space complexity.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Initial Total Sum (rSum):

    * Compute the total sum of the array (rSum) in the first loop. This represents the initial value of the "right sum," assuming no elements are in the left part of the array.
2. Iterate Through the Array:

    * Traverse the array from the beginning to the second-to-last element.
    For each index:
        *  Add the current element to the left sum (lSum).
        * Subtract the same element from the right sum (rSum).
3. Check Valid Split:

   *  Compare lSum and rSum for each split point. If lSum is greater than or equal to rSum, increment the validSplit counter.
4. Return the Count:

    * Return the total number of valid splits stored in validSplit.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
 O(n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(1) 

# Code
```cpp []
class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        int n = nums.size(); // Number of elements in the array
        long long rSum = 0;  // Stores the cumulative sum of elements on the right side of the split
        long long lSum = 0;  // Stores the cumulative sum of elements on the left side of the split
        int validSplit = 0;  // Counter for valid splits

        // Step 1: Calculate the total sum of the array (initial right sum)
        for (int i : nums) {
            rSum += i;
        }

        // Step 2: Iterate through the array to calculate left and right sums dynamically
        for (int i = 0; i < n - 1; i++) {
            lSum += nums[i];   // Add the current element to the left sum
            rSum -= nums[i];   // Subtract the current element from the right sum

            // Step 3: Check if the current split is valid
            if (lSum >= rSum) {
                validSplit++; // Increment the counter if the condition is satisfied
            }
        }

        // Step 4: Return the total count of valid splits
        return validSplit;
    }
};

```


# Method 2 of Doing the same 


# Intuition

To solve the problem of splitting an array into two non-empty parts such that the left sum `(lSum)` is greater than or equal to the right sum `(rSum)`, this approach precomputes and stores suffix sums for efficient access during the main loop.

Instead of recalculating the right sum `(rSum)` dynamically, we use an `unordered_map to store the suffix sums for all indices`. This ensures that for each split point, the right sum can be directly accessed in constant time. However, this approach trades memory usage for simplicity in accessing suffix sums.

# Approach
1. Precompute Suffix Sums:

   *  Use an unordered_map to store the suffix sum (rSum) for each index from the end of the array.
   *  Traverse the array from right to left and compute the cumulative sum, storing it in the map.
2. Calculate Left Sum Dynamically:

   *  Traverse the array from left to right, maintaining the cumulative left sum (lSum).
   *  For each split point, compare lSum with the precomputed rSum for the next index.
3. Count Valid Splits:

  *   Increment the validSplit counter whenever lSum is greater than or equal to rSum for a given split point.
4. Return the Count:

   *  Finally, return the total number of valid splits stored in validSplit.


# Complexity 
- Time Complexity -
    * O(n): One pass to compute the suffix sums and another pass to calculate the prefix sums and perform comparisons.

- Space Complexity -
    * O(n): Additional storage for the suffix sums in the unordered_map.

## Code
```cpp []
class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        // Edge case: If the array is empty, there are no valid splits
        if (nums.size() == 0) {
            return 0;
        }

        // Step 1: Precompute suffix sums and store them in a map
        unordered_map<int, long long> mp; // Stores suffix sums with index as the key
        long long sum = 0; // To compute the cumulative sum from the right
        for (int i = nums.size() - 1; i >= 0; i--) {
            sum += nums[i]; // Add the current element to the suffix sum
            mp[i] = sum;    // Store the suffix sum in the map with the current index as the key
        }

        // Step 2: Traverse the array to calculate prefix sums dynamically
        int validSplit = 0; // Counter for valid splits
        sum = 0; // Reset sum to calculate the left sum (prefix sum)
        for (int i = 0; i < nums.size() - 1; i++) {
            sum += nums[i]; // Add the current element to the left sum
            // Check if the left sum is greater than or equal to the right sum
            if (sum >= mp[i + 1]) {
                validSplit++; // Increment the counter if the condition is satisfied
            }
        }

        // Step 3: Return the total count of valid splits
        return validSplit;
    }
};

```


# Key Differences from Optimized Code

   *  Uses an unordered_map to store suffix sums, which requires extra space.
  *   Instead of dynamically updating the right sum (rSum), this approach precomputes and accesses it directly from the map.
  *   Trades memory usage for simplicity in accessing suffix sums.

# Takeaway

While this approach works efficiently for smaller arrays, it can become memory-intensive for larger inputs due to the additional storage required for the unordered_map. The dynamic sum update method (optimized approach) is generally preferred for space efficiency.




# Please UpVote If you like .... !!!
['Array', 'Sliding Window', 'Suffix Array', 'Prefix Sum', 'C++']