Split Array into Two Equal Sum Subarrays

Problem Statement

Given an integer array arr[], determine whether it can be split into two contiguous subarrays such that the sum of both parts is equal.

• You cannot reorder elements.

• Both subarrays must be non-empty.

Key Insight (Concept)

To split the array into two parts with equal sum:

• Let total sum = S

• For two equal parts:
  Each part must have sum = S / 2

This leads to two important observations:

1. If S is odd, splitting is impossible.

If S is even, we just need to check:

Is there a prefix whose sum = S / 2?

This is where the prefix sum concept comes in.

Prefix Sum Idea

A prefix sum is the running total as we traverse the array:

Example:

arr = [1, 2, 3, 4]

Prefix sums:
1
1 + 2 = 3
3 + 3 = 6
6 + 4 = 10

We check if any prefix equals totalSum / 2.

Java Implementation

class Solution {
    public boolean canSplit(int arr[]) {
        int total = 0;
        
        // Step 1: Calculate total sum
        for (int num : arr) {
            total += num;
        }
        
        // Step 2: If total sum is odd → cannot split
        if (total % 2 != 0) return false;
        
        int target = total / 2;
        int prefixSum = 0;
        
        // Step 3: Traverse and check prefix sum
        for (int i = 0; i < arr.length - 1; i++) {
            prefixSum += arr[i];
            
            if (prefixSum == target) {
                return true;
            }
        }
        
        return false;
    }
}

How the Code Works

Step 1: Compute Total Sum

We sum all elements in the array.

Step 2: Check Even/Odd

• If total is odd → return false

• If even → proceed

Step 3: Find Prefix with Half Sum

We keep adding elements and check:

prefixSum == total / 2

If yes → valid split exists.

Example 1

Input:

arr = [1, 2, 3, 4, 5, 5]

Step-by-step:

Total sum = 20
Target = 10

Prefix sums:
1
3
6
10   Found!

Output:

true

Explanation:

Split as:

[1, 2, 3, 4]  → sum = 10
[5, 5]        → sum = 10

Example 2

Input:

arr = [4, 3, 2, 1]

Step-by-step:

Total sum = 10
Target = 5

Prefix sums:
4
7 (exceeds target)

No prefix equals 5.

Output:

false

Complexity Analysis

• Time Complexity: O(n)
  (Single pass through array)

• Space Complexity: O(1)
  (No extra space used)

Summary

• Convert the problem into a prefix sum check

• Ensure total sum is even

• Look for a prefix equal to half of total sum

• Efficient and optimal solution in linear time