Partition Array Into Three Parts With Equal Sum — Solution
Partition Array Into Three Parts With Equal Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Partition Array Into Three Parts With Equal Sum is an easy coding problem on arrays, greedy and prefix sum, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Greedy, Prefix Sum
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of integers arr, return true if it can be partitioned into three non-empty contiguous parts with equal sums.
Formally, you need indices i < j with i + 1 < j such that arr[0..i], arr[i+1..j-1] and arr[j..n-1] all have the same sum.
Example 1
Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0+2+1-6 = 6-7+9-1... the three parts each sum to 3.
Example 2
Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false
Example 3
Input: arr = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: Each part sums to 6.
Constraints
3 <= arr.length <= 50000-10000 <= arr[i] <= 10000
Hints for Partition Array Into Three Parts With Equal Sum
Hint 1
If the total is not divisible by 3 the answer is immediately
false.Hint 2
Sweep once, cutting greedily the moment the running sum reaches one third, then two thirds.
Hint 3
The third part must be non-empty — check that the second cut happens before the last index.
How to solve Partition Array Into Three Parts With Equal Sum
The two cut positions are forced: the first must land where the prefix sum first hits total/3, and the second where it first hits 2·total/3. Cutting later can never help.
Approach
- Sum the array. If
total % 3 != 0, returnfalse. - Set
part = total / 3and sweep with a running prefixacc, counting cuts made. - When
accequalspart * (cuts + 1), take the cut. - Return
trueas soon as the second cut is taken at an index strictly before the last, so the third part is non-empty.
Why it works
Prefix sums are the only quantity that matters, and the earliest index reaching each threshold leaves the most room for the remaining parts. Because the trailing part is fixed by the second cut, taking cuts greedily is optimal.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Zeros make prefix sums plateau, so the running sum can equal
partmany times — count cuts, do not re-trigger on the same threshold. - Allowing the second cut at the final index yields an empty third part.
total % 3on negative totals still works in every language here because the check is against0, but the divisibility test must precede the division.
Reference solution
Python
from typing import List
def canThreePartsEqualSum(arr: List[int]) -> bool:
total = sum(arr)
if total % 3 != 0:
return False
part = total // 3
acc = 0
found = 0
for i, x in enumerate(arr):
acc += x
if acc == part * (found + 1):
found += 1
if found == 2 and i < len(arr) - 1:
return True
return FalseJava
public static boolean canThreePartsEqualSum(int[] arr) {
long total = 0;
for (int x : arr) total += x;
if (total % 3 != 0) return false;
long part = total / 3;
long acc = 0;
int found = 0;
for (int i = 0; i < arr.length; i++) {
acc += arr[i];
if (acc == part * (found + 1)) {
found++;
if (found == 2 && i < arr.length - 1) return true;
}
}
return false;
}C++
bool canThreePartsEqualSum(vector<int>& arr) {
long long total = 0;
for (int x : arr) total += x;
if (total % 3 != 0) return false;
long long part = total / 3;
long long acc = 0;
int found = 0;
for (int i = 0; i < (int) arr.size(); i++) {
acc += arr[i];
if (acc == part * (found + 1)) {
found++;
if (found == 2 && i < (int) arr.size() - 1) return true;
}
}
return false;
}JavaScript
var canThreePartsEqualSum = function(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) total += arr[i];
if (total % 3 !== 0) return false;
const part = total / 3;
let acc = 0, found = 0;
for (let i = 0; i < arr.length; i++) {
acc += arr[i];
if (acc === part * (found + 1)) {
found++;
if (found === 2 && i < arr.length - 1) return true;
}
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms