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
- Calculate
totalSum, the sum of every element in the array. - If
totalSum % 3 != 0, returnfalseimmediately since three equal integer parts are impossible. - Compute
target = totalSum / 3, the sum each of the three parts must achieve. - Walk through the array from index 0 up to (but not including) the last index, accumulating a
runningSum. - Each time
runningSumequalstarget, increment apartsFoundcounter and resetrunningSumback to 0. - Return
trueas soon aspartsFoundreaches 2, because the remaining suffix of the array automatically sums totargetas well. - If the loop finishes without
partsFoundreaching 2, returnfalse.
Java Program
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
totalSumaccumulates the sum of every element inarrin a single pass.- If
totalSum % 3 != 0, the method returnsfalseright away since no integer target sum exists. targetis set tototalSum / 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. runningSumaccumulates elements until it equalstarget, at which pointpartsFoundincrements andrunningSumresets to 0 to start tracking the next part.- As soon as
partsFoundreaches 2, the method returnstruebecause the remaining elements must also sum totarget, since the total is exactly3 * 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 |
|---|---|---|---|---|
| 0 | 3 | 0 | 3 (match, reset to 0) | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 0 | 1 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 3 | 0 | 3 (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.
int[] arr = {0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1};
boolean result = canThreePartsEqualSum(arr);
// result = trueExample 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.
int[] arr = {1, 2, 3};
boolean result = canThreePartsEqualSum(arr);
// result = falseExample 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.
int[] arr = {10, -10, 10, -10, 10, -10, 10};
boolean result = canThreePartsEqualSum(arr);
// result = falseCommon 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 / 3directly truncates whentotalSumisn’t a multiple of 3 (for example,totalSum = 10givestarget = 3, not a real third). Always returnfalsewhentotalSum % 3 != 0before computingtarget. - Scanning through the last index – letting the loop run to
arr.lengthinstead ofarr.length - 1lets the second split point land on the final element, leaving the third part empty even though the method reportstrue. Bound the loop atarr.length - 1. - Forgetting to reset runningSum – skipping the reset after the first match means the second part’s sum is compared against
targetwhile still carrying the first part’s total, so a valid split is missed. ResetrunningSumto 0 immediately after incrementingpartsFound. - 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 againsttarget, not index position. - Using inequality comparisons with negative numbers – checking
runningSum >= targetinstead ofrunningSum == targetbreaks once negative numbers are present, because the running sum can overshoot and never land ontargetexactly. 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
partsFoundreaches 2 instead of returning immediately, recording each index where the running sum returns totarget. - What if the array must be split into k equal-sum parts instead of three? – generalize
target = totalSum / kand count matches up tok - 1, still bailing out early whentotalSum % 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
targetis 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/



