Split An Array Into Two Equal Sum Subarrays

Given an array of integers arr, return true if it is possible to split it in two subarrays (without reordering the elements), such that the sum of the two subarrays are equal. If it is not possible then return false.

Examples:

Input: arr = [1, 2, 3, 4, 5, 5]
Output: true
Explanation: In the above example, we can divide the array into two subarrays with eqaul sum. The two subarrays are: [1, 2, 3, 4] and [5, 5]. The sum of both the subarrays are 10. Hence, the answer is true.

Input: arr = [4, 3, 2, 1]
Output: false
Explanation: In the above example, we cannot divide the array into two subarrays with eqaul sum. Hence, the answer is false.

Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Constraints:
1<=arr.size()<=10⁵ 
1<=arr[i]<=10⁶

Approach 01:

#include <vector>

class Solution {
  public:
    bool canSplit(std::vector<int>& numbers) {
        long long int totalSum = 0;
        for (int i = 0; i < numbers.size(); i++) {
            totalSum += numbers[i];  // Calculate the total sum of the array
        }
        
        long long int leftSum = 0;
        for (int i = 0; i < numbers.size(); i++) {
            leftSum += numbers[i];   // Accumulate the sum on the left side
            totalSum -= numbers[i];  // Decrease the current element from the total sum to get the right side sum
            
            if (leftSum == totalSum) {
                return true;  // If both sides are equal, return true
            }
        }
        
        return false;  // Return false if no such point is found
    }

};

class Solution:
    def canSplit(self, numbers):
        totalSum = sum(numbers)  # Calculate the total sum of the array
        
        leftSum = 0
        for number in numbers:
            leftSum += number  # Accumulate the sum on the left side
            totalSum -= number  # Decrease the current element from the total sum to get the right side sum
            
            if leftSum == totalSum:
                return True  # If both sides are equal, return true
        
        return False  # Return false if no such point is found

Time Complexity

• Calculating the Total Sum:

  In the first loop, we calculate the total sum of the array, which takes \( O(n) \) time, where \( n \) is the size of the numbers array.

• Checking for a Split Point:

  In the second loop, we iterate over the array again to check if a split point exists where the sum of elements on the left equals the sum of elements on the right. This also takes \( O(n) \) time.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \) as both loops run sequentially.

Space Complexity

• Space Usage:

  The algorithm uses a constant amount of extra space, \( O(1) \), for storing variables like totalSum and leftSum. No additional data structures are used that grow with the input size.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).