Split an array into two equal Sum subarrays

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Check if array can be split into two parts with equal sum. Prefix sum check.

Algorithm

1Total sum must be even. Find index where prefix sum = total/2.

Common Pitfalls

•O(n). Total odd: impossible. Find split point where prefix sum equals half.

Split an array into two equal Sum subarrays.java

Java

// Approach: Compute total sum; if odd, impossible. Find split point where left prefix sum = sum/2.
// Time: O(n) Space: O(1)
class Solution {
    public boolean canSplit(int arr[]) {
        int sum = 0;
        for (int a : arr)
            sum += a;

        int temp = 0;
        for (int a : arr) {
            temp += a;
            if (temp == (sum - temp))
                return true;
        }

        return false;
    }
}

Was this solution helpful?