Split array in three equal sum subarrays

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Check if array can be split into 3 parts with equal sum. Prefix sum to find two split points.

Algorithm

1Total sum must be divisible by 3. Find first index with prefix sum = total/3, then find second index with prefix sum = 2*total/3.

Common Pitfalls

•O(n). Enumerate split points with prefix sum tracking. Return indices (not values).

Split array in three equal sum subarrays.java

Java

// Approach: Find prefix sum/3 and 2*sum/3 split points. Track positions where these exact sums occur.
// Time: O(n) Space: O(n)
class Solution {
    // Function to determine if array arr can be split into three equal sum sets.
    public List<Integer> findSplit(int[] arr) {
        List<Integer> result = new ArrayList<>(Arrays.asList(-1, -1));
        int totalSum = 0;

        for (int num : arr)
            totalSum += num;

        if (totalSum % 3 != 0)
            return result;

        int targetSum = totalSum / 3;
        int currentSum = 0;
        int firstIndex = -1, secondIndex = -1;

        for (int i = 0; i < arr.length; i++) {
            currentSum += arr[i];

            if (currentSum == targetSum && firstIndex == -1)
                firstIndex = i;

            else if (currentSum == 2 * targetSum && firstIndex != -1) {
                secondIndex = i;
                result.set(0, firstIndex);
                result.set(1, secondIndex);
                return result;
            }
        }

        return result;
    }
}

Was this solution helpful?