Two Equal Sum Subarrays

Intuition

We are looking for a cut index after which the sum on the left equals the sum on the right. Instead of computing both halves independently for each candidate cut, maintain two running accumulators: a prefix sum (growing left-to-right) and a suffix sum (shrinking left-to-right). Start with prefix=0 and suffix=total. After including each element in the prefix and excluding it from the suffix, check for equality. If the total sum is odd, no equal-half split can exist, but the loop handles this gracefully — prefix and suffix will never both be whole-number halves.

Algorithm

1Compute `suff` = sum of all elements in `arr`.
2Initialise `pre = 0`.
3For each element `x` in `arr`: `pre += x`, `suff -= x`.
4If `pre == suff`, return `true`.
5After the loop, return `false`.

Example Walkthrough

Input: arr = [1, 2, 3, 3]

1.Total sum = 9. suff = 9, pre = 0.
2.x=1: pre=1, suff=8. 1 ≠ 8.
3.x=2: pre=3, suff=6. 3 ≠ 6.
4.x=3: pre=6, suff=3. 6 ≠ 3.
5.x=3: pre=9, suff=0. 9 ≠ 0.
6.No equal split found → return false.

Output: false

Common Pitfalls

•The split point is exclusive of the dividing element — prefix includes up to and including index i, suffix covers i+1 onward.
•An odd total sum makes an equal split mathematically impossible; the check `pre == suff` will simply never be true.
•This problem does not require the two parts to be contiguous halves of exactly N/2 elements — just that the sums match at some cut point.

Two Equal Sum Subarrays.java

Java


// Approach: We want to find a split point where the sum of the left part equals the sum of the right part.
// First compute the total sum as the initial 'suffix'. Then walk left-to-right, growing the prefix and
// shrinking the suffix by the current element. Whenever prefix == suffix, a valid split exists.
// Note: if the total sum is odd, no equal split is possible — but the loop handles this naturally.
//
// Time: O(N) — two linear passes over the array.
// Space: O(1) — only two integer accumulators.

class Solution {

    public boolean canSplit(int arr[]) {
        int suff = 0;
        int pre = 0;
        for (int i : arr) {
            suff += i;
        }

        for (int i : arr) {
            pre += i;
            suff -= i;

            if (pre == suff) {
                return true;
            }
        }
        return false;
    }
}

Was this solution helpful?