Split an array into two equal Sum subarrays

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

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

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?