Advertisement
Home Data Structure Arrays Split Array into Three Equal Sum Parts

Split Array into Three Equal Sum Parts

0
Advertisement

Title: Split Array into Three Equal Sum Parts

Splitting an array into three parts with equal sums is a classic prefix-sum problem that shows up often in coding interviews. In this guide, you’ll learn how to check whether an integer array arr can be divided into three non-empty contiguous parts where each part has the same sum, along with a complete Java implementation, a step-by-step trace, and the edge cases worth testing.

Understanding the Problem

Given an array of integers, the task is to determine if it is possible to cut the array into three contiguous, non-empty parts such that the sum of elements in each part is exactly the same. For example, [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1] can be split into [0, 2, 1], [-6, 6, -7, 9, 1], and [2, 0, 1], each summing to 3.

The key insight is that you never need to search for three separate subarray sums independently. If the total sum of the array is divisible by 3, the target sum for each part is totalSum / 3. From there, a single forward pass that tracks a running sum and counts how many times it hits the target is enough to decide the answer.

Approach / Algorithm Steps

  1. Calculate totalSum, the sum of every element in the array.
  2. If totalSum % 3 != 0, return false immediately since three equal integer parts are impossible.
  3. Compute target = totalSum / 3, the sum each of the three parts must achieve.
  4. Walk through the array from index 0 up to (but not including) the last index, accumulating a runningSum.
  5. Each time runningSum equals target, increment a partsFound counter and reset runningSum back to 0.
  6. Return true as soon as partsFound reaches 2, because the remaining suffix of the array automatically sums to target as well.
  7. If the loop finishes without partsFound reaching 2, return false.

Java Program

Java
public class ThreePartEqualSum {

    public static boolean canThreePartsEqualSum(int[] arr) {
        int totalSum = 0;
        for (int num : arr) {
            totalSum += num;
        }

        if (totalSum % 3 != 0) {
            return false;
        }

        int target = totalSum / 3;
        int runningSum = 0;
        int partsFound = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            runningSum += arr[i];
            if (runningSum == target) {
                partsFound++;
                runningSum = 0;
                if (partsFound == 2) {
                    return true;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[] arr1 = {0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1};
        int[] arr2 = {1, 2, 3};
        int[] arr3 = {10, -10, 10, -10, 10, -10, 10};

        System.out.println(canThreePartsEqualSum(arr1));
        System.out.println(canThreePartsEqualSum(arr2));
        System.out.println(canThreePartsEqualSum(arr3));
    }
}

Explanation of the Program

  • totalSum accumulates the sum of every element in arr in a single pass.
  • If totalSum % 3 != 0, the method returns false right away since no integer target sum exists.
  • target is set to totalSum / 3, the sum each of the three parts must equal.
  • The second loop only scans up to arr.length - 1, so the last element always belongs to the third part, keeping it non-empty.
  • runningSum accumulates elements until it equals target, at which point partsFound increments and runningSum resets to 0 to start tracking the next part.
  • As soon as partsFound reaches 2, the method returns true because the remaining elements must also sum to target, since the total is exactly 3 * target.

Step-by-Step Trace

Consider arr = [3, 0, 0, 0, 3, 0, 0, 0, 3], where the expected output is true. The total sum is 9, so target = 3. Here is how runningSum and partsFound change as the loop scans from i = 0:

Iteration (i)arr[i]runningSum (before)runningSum (after)partsFound
0303 (match, reset to 0)1
10001
20001
30001
4303 (match)2, loop returns true

At the end of each iteration, runningSum holds the sum of elements accumulated since the last time it matched target, and the loop stops as soon as partsFound reaches 2 because the untouched suffix of the array is guaranteed to sum to target as well.

Examples

Example 1: A Valid Split with Mixed Signs

The array [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1] splits into [0, 2, 1], [-6, 6, -7, 9, 1], and [2, 0, 1], each summing to 3.

Java
int[] arr = {0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1};
boolean result = canThreePartsEqualSum(arr);
// result = true

Example 2: Divisible Sum but No Valid Split

The array [1, 2, 3] has a total sum of 6, which is divisible by 3, but the only way to divide it into three non-empty contiguous parts is [1], [2], [3], whose sums are not equal.

Java
int[] arr = {1, 2, 3};
boolean result = canThreePartsEqualSum(arr);
// result = false

Example 3: Sum Not Divisible by Three

The array [10, -10, 10, -10, 10, -10, 10] sums to 10, which fails the totalSum % 3 != 0 check, so the method returns false without scanning for split points.

Java
int[] arr = {10, -10, 10, -10, 10, -10, 10};
boolean result = canThreePartsEqualSum(arr);
// result = false

Common Mistakes to Avoid

Most bugs in this problem come from the integer-division target check and the exact loop boundary, not from the core logic. Watch for these specifically:

  • Skipping the divisibility check – computing target = totalSum / 3 directly truncates when totalSum isn’t a multiple of 3 (for example, totalSum = 10 gives target = 3, not a real third). Always return false when totalSum % 3 != 0 before computing target.
  • Scanning through the last index – letting the loop run to arr.length instead of arr.length - 1 lets the second split point land on the final element, leaving the third part empty even though the method reports true. Bound the loop at arr.length - 1.
  • Forgetting to reset runningSum – skipping the reset after the first match means the second part’s sum is compared against target while still carrying the first part’s total, so a valid split is missed. Reset runningSum to 0 immediately after incrementing partsFound.
  • Thinking in equal lengths instead of equal sums – trying to cut the array into three equal-size chunks fails on inputs like [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1], where the valid parts have different lengths. Track cumulative sum against target, not index position.
  • Using inequality comparisons with negative numbers – checking runningSum >= target instead of runningSum == target breaks once negative numbers are present, because the running sum can overshoot and never land on target exactly. Always compare for exact equality.

Edge Cases to Test

A thorough answer calls out these boundary inputs before being asked:

  • Array with fewer than three elements
  • Total sum not divisible by three
  • All elements equal to zero
  • Negative numbers present
  • Multiple positions where the running sum matches target
  • Single valid split with one part containing most of the elements
  • Integer.MAX_VALUE or Integer.MIN_VALUE present
  • All elements identical and non-zero

Additional Considerations

The algorithm makes two linear passes over arr: one to compute totalSum and one to scan for the split points, so the overall time complexity is O(n). Space complexity is O(1) since only a handful of int variables are used regardless of input size.

Because totalSum and runningSum are plain int values, an array whose elements sum beyond Integer.MAX_VALUE will overflow silently and produce an incorrect target. If the input can contain very large numbers, accumulate both sums in a long instead.

Interview Follow-up Questions

Once the base solution is working, interviewers often push into these variations:

  • What if you need every valid pair of split indices instead of just confirming one exists? – keep scanning after partsFound reaches 2 instead of returning immediately, recording each index where the running sum returns to target.
  • What if the array must be split into k equal-sum parts instead of three? – generalize target = totalSum / k and count matches up to k - 1, still bailing out early when totalSum % k != 0.
  • What if the input is read-only and must be processed without extra storage? – the existing approach already uses only O(1) extra space, since it never copies the array or builds a prefix-sum table.
  • What if the array has hundreds of millions of elements and must be processed in parallel? – compute partial sums per chunk in parallel, merge the chunk sums sequentially to find the global total, then run a second parallel pass per chunk to locate the two split points once target is known.

Conclusion

Checking whether an array splits into three equal-sum parts comes down to one pass to total the array and one pass to locate two split points where a running sum matches totalSum / 3. The early divisibility check and the loop bound of arr.length - 1 are the two details that most often trip up a first attempt.

Try adapting canThreePartsEqualSum to return the actual split indices instead of a boolean, or extend it to an arbitrary number of parts. You can learn more about array-based interview problems in the Arrays category: https://dailyjavaconcept.com/category/arrays/