Split Array Equal Sums

The problem asks us to find a "pivot" index $i$ such that the sum of all elements from the start of the array up to $i$ equals the sum of the remaining elements. This is a classic partitioning problem that tests your understanding of array traversal and prefix sums.

Overview

The core idea is to split the array into a Left Subarray $[0 \dots i]$ and a Right Subarray $[i+1 \dots n-1]$.

For any index $i$, if we know the sum of the elements to the left (including $i$) and the total sum of the entire array, we can calculate the right sum instantly: $$\text{Right Sum} = \text{Total Sum} - \text{Left Sum}$$ The goal is to find the first $i$ where $\text{Left Sum} = \text{Right Sum}$.

Brute Force

In a brute force approach, we would iterate through every possible split index $i$. For each index, we would run two nested loops: one to calculate the sum of the left part and another to calculate the sum of the right part.

def split_array_equal_sums(array: list[int]) -> int:
    n = len(array)
    # Iterate through every possible split index i
    for i in range(n - 1):
        left_sum = 0
        right_sum = 0
        
        # Calculate sum of elements from 0 to i
        for j in range(i + 1):
            left_sum += array[j]
            
        # Calculate sum of elements from i+1 to n-1
        for k in range(i + 1, n):
            right_sum += array[k]
            
        if left_sum == right_sum:
            return i
            
    return -1

• Time complexity: O(N²) — For each of the $N$ possible split points, we iterate through the array to calculate sums.
• Space complexity: O(1) — No extra data structures are used beyond a few integer variables.

Optimal / Best Approach

We can optimize the brute force by observing that we don't need to re-sum the entire array for every index. By pre-calculating the Total Sum of the array, we can maintain a running left_sum as we iterate.

1. Calculate the total_sum of the array once.
2. Initialize left_sum to 0.
3. Iterate through the array. For each element at index i:
   • Add array[i] to left_sum.
   • Calculate right_sum as total_sum - left_sum.
   • If left_sum == right_sum, return $i$.
4. If the loop finishes without a match, return -1.

def split_array_equal_sums(array: list[int]) -> int:
    total_sum = sum(array)
    left_sum = 0
    
    # We iterate up to n-1 because the right subarray 
    # must contain at least one element (index i+1)
    for i in range(len(array) - 1):
        left_sum += array[i]
        right_sum = total_sum - left_sum
        
        if left_sum == right_sum:
            return i
            
    return -1

• Time complexity: O(N) — We pass through the array once to get the total sum and once more to find the split index.
• Space complexity: O(1) — We only store two integer variables regardless of the input size.

Why This Works

The equation $\text{Left Sum} = \text{Right Sum}$ implies that $\text{Left Sum} = \frac{1}{2} \times \text{Total Sum}$.

This means:

1. If the total sum is odd, no valid integer split can exist (since all elements are positive integers).
2. The first index where the running sum hits exactly half of the total sum is our answer. Because all elements are positive, the left_sum is strictly increasing, guaranteeing that the first valid index we find is the only possible one (or the leftmost one).

Edge Cases

• Smallest Array: If the array is [10, 10], the total sum is 20. At index 0, left_sum is 10 and right_sum is 10. Returns 0.
• No Split Possible: In [1, 2, 3], sums are 1 vs 5, and 3 vs 3 is impossible because index 2 would leave no elements for the right subarray.

Fast