Partition Array Into Three Parts With Equal Sum solution and explanation
Google
9 more videos on this problem
Leetcode 1013 Partition Array Into Three Parts With Equal SumRen Zhang · 5:53 · 3K views
LeetCode : Partition Array Into Three Parts With Equal SumBinary Beast · 5:07 · 2K views
LeetCode 1013 : Partition Array Into Three Parts With Equal Sum || EASY || C++ || JAVA || SolutionCodeGPT · 13:46 · 866 views
1013. Partition Array Into Three Parts With Equal Sum (Leetcode Easy)Programming Live with Larry · 16:41 · 819 views
LeetCode 1013 Partition Array Into Three Parts With Equal Sum - PythonRan Fang · 7:19 · 440 views
LeetCode 1013 | Partition Array Into Three Parts With Equal Sum | Array | JavaSleepy Cracker · 7:10 · 390 views
Leetcode 1013 Partition Array Into Three Parts With Equal SumMath Geeks · 3:17 · 306 views
Leetcode 1013 - Partition Array Into Three Parts With Equal SumShafik Quoraishee · 13:53 · 293 views
1013. Partition Array Into Three Parts With Equal Sum 将数组分成和相等的三个部分【LeetCode 题解】LeetCode 力扣 · 6:16 · 177 views
Leetcode 1013 Partition Array Into Three Parts With Equal Sum - In Hindi ExplanationAlgorithmicIQ · 10:22 · 106 views
The problem
Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums.
Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])
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 = 2 + 0 + 1
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: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
Constraints:
3 <= arr.length <= 5 * 104-104 <= arr[i] <= 104
Approach overview
Problem Overview: You are given an integer array and need to determine whether it can be split into three non‑empty contiguous parts such that each part has the same sum. The partition must preserve the original order of elements.
The key observation: if the total sum of the array is not divisible by 3, forming three equal partitions is impossible. When the sum is divisible by 3, the target for each segment becomes totalSum / 3. The task then reduces to finding two cut points where the prefix sums reach this value.
Approach 1: Prefix Sum and Count Approach (O(n) time, O(1) space)
This approach scans the array once while maintaining a running prefix sum. First compute the total sum and verify it is divisible by three. Then iterate through the array and increment a counter every time the running sum equals target = totalSum / 3. Once this happens, reset the running sum to zero and continue scanning the remaining elements.
If you can form at least three segments whose sums equal the target, the array can be partitioned correctly. The algorithm relies on the prefix sum concept: when the cumulative sum reaches the target, you have found one valid partition boundary. Because the array is processed in a single pass and no extra data structures are required, the time complexity stays O(n) and space complexity O(1). This technique is common in problems involving arrays and cumulative sums.
Approach 2: Two Pointer Approach (O(n) time, O(1) space)
This method uses a greedy scan with implicit partition boundaries. After verifying the total sum is divisible by three, compute the target sum for each partition. Move a pointer from the start while accumulating a running sum until it equals the target. That fixes the first partition. Continue scanning to locate the second segment that also sums to the same target.
The remaining elements automatically form the third partition. If all three segments match the target sum and each segment is non‑empty, the condition holds. The logic works because once the first two segments reach the required sum, the remainder must also equal the target due to the total sum constraint. This greedy reasoning is typical for problems under greedy strategies combined with array traversal.
Recommended for interviews: The Prefix Sum and Count approach is what most interviewers expect. It demonstrates that you recognize the divisibility condition and can convert the problem into finding prefix segments with a fixed target sum. The Two Pointer variant expresses the same idea with slightly different reasoning and also runs in optimal O(n) time with constant space.
Approach 1: Prefix Sum and Count Approach
This approach works by first calculating the total sum of the array. If the sum is not divisible by 3, then it is not possible to partition it into three equal parts. Otherwise, we calculate one-third of this sum (this is the target sum for each of the three parts).
We then iterate over the array, keeping a running sum. Every time the running sum reaches one of the target sums, we reset the running sum and count this as one successful partition. If we get two successful partitions by the time we reach the end, the array can be partitioned as required.
def canThreePartsEqualSum(arr):
totalSum = sum(arr)
if totalSum % 3 != 0:
return False
target = totalSum // 3
currSum, parts = 0, 0
for num in arr:
currSum += num
if currSum == target:
parts += 1
currSum = 0
return parts >= 3
# Example usage
arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4]
print(canThreePartsEqualSum(arr)) # Output: Truepublic class Solution {
public boolean canThreePartsEqualSum(int[] arr) {
int totalSum = 0;
for (int num : arr) {
totalSum += num;
}
if (totalSum % 3 != 0) return false;
int target = totalSum / 3;
int currSum = 0, parts = 0;
for (int num : arr) {
currSum += num;
if (currSum == target) {
parts++;
currSum = 0;
}
}
return parts >= 3;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
System.out.println(solution.canThreePartsEqualSum(arr)); // Output: true
}
}#include <vector>
#include <iostream>
using namespace std;
bool canThreePartsEqualSum(vector<int>& arr) {
int totalSum = 0;
for (int num : arr) {
totalSum += num;
}
if (totalSum % 3 != 0) return false;
int target = totalSum / 3;
int currSum = 0, parts = 0;
for (int num : arr) {
currSum += num;
if (currSum == target) {
parts++;
currSum = 0;
}
}
return parts >= 3;
}
int main() {
vector<int> arr = {3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
cout << (canThreePartsEqualSum(arr) ? "true" : "false") << endl;
return 0;
}function canThreePartsEqualSum(arr) {
const totalSum = arr.reduce((acc, val) => acc + val, 0);
if (totalSum % 3 !== 0) return false;
const target = totalSum / 3;
let currSum = 0, parts = 0;
for (const num of arr) {
currSum += num;
if (currSum === target) {
parts++;
currSum = 0;
}
}
return parts >= 3;
}
// Example usage
const arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4];
console.log(canThreePartsEqualSum(arr)); // Output: true#include <stdbool.h>
#include <stdio.h>
bool canThreePartsEqualSum(int* arr, int arrSize) {
int totalSum = 0;
for (int i = 0; i < arrSize; i++) {
totalSum += arr[i];
}
if (totalSum % 3 != 0) return false;
int target = totalSum / 3;
int currSum = 0, parts = 0;
for (int i = 0; i < arrSize; i++) {
currSum += arr[i];
if (currSum == target) {
parts++;
currSum = 0;
}
}
return parts >= 3;
}
int main() {
int arr[] = {3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
int size = sizeof(arr) / sizeof(arr[0]);
printf("%s\n", canThreePartsEqualSum(arr, size) ? "true" : "false");
return 0;
}using System;
public class Solution {
public bool CanThreePartsEqualSum(int[] arr) {
int totalSum = 0;
foreach (int num in arr) {
totalSum += num;
}
if (totalSum % 3 != 0) return false;
int target = totalSum / 3;
int currSum = 0, parts = 0;
foreach (int num in arr) {
currSum += num;
if (currSum == target) {
parts++;
currSum = 0;
}
}
return parts >= 3;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] arr = {3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
Console.WriteLine(solution.CanThreePartsEqualSum(arr) ? "true" : "false");
}
}The Python version uses the sum() function to calculate the total and checks divisibility by 3. It uses a loop to gather partitions of the target sum.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Two Pointer Approach
This approach is similar to the prefix sum method but uses two pointers to track the start and the end of the array. The two pointers search for sections whose sums are equal to the target. As soon as both sections with the required sum are found, the middle section is naturally what remains, fulfilling the condition.
Since we want three equal parts, we avoid iterating over the entire array as soon as two parts are found. The partitioning is ensured by keeping one pointer from the left and another from the right.
def canThreePartsEqualSum(arr):
totalSum = sum(arr)
if totalSum % 3 != 0:
return False
target = totalSum // 3
leftSum, rightSum = 0, 0
i, j = 0, len(arr) - 1
while i < j:
if leftSum != target:
leftSum += arr[i]
i += 1
if rightSum != target:
rightSum += arr[j]
j -= 1
if leftSum == target and rightSum == target:
return True
return False
# Example usage
arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4]
print(canThreePartsEqualSum(arr)) # Output: Truepublic class Solution {
public boolean canThreePartsEqualSum(int[] arr) {
int totalSum = 0;
for (int num : arr) {
totalSum += num;
}
if (totalSum % 3 != 0) return false;
int target = totalSum / 3;
int leftSum = 0, rightSum = 0, i = 0, j = arr.length - 1;
while (i < j) {
if (leftSum != target) {
leftSum += arr[i++];
}
if (rightSum != target) {
rightSum += arr[j--];
}
if (leftSum == target && rightSum == target) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
System.out.println(solution.canThreePartsEqualSum(arr)); // Output: true
}
}#include <vector>
#include <iostream>
using namespace std;
bool canThreePartsEqualSum(vector<int>& arr) {
int totalSum = 0;
for (int num : arr) {
totalSum += num;
}
if (totalSum % 3 != 0) return false;
int target = totalSum / 3;
int leftSum = 0, rightSum = 0, i = 0, j = arr.size() - 1;
while (i < j) {
if (leftSum != target) {
leftSum += arr[i++];
}
if (rightSum != target) {
rightSum += arr[j--];
}
if (leftSum == target && rightSum == target) {
return true;
}
}
return false;
}
int main() {
vector<int> arr = {3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
cout << (canThreePartsEqualSum(arr) ? "true" : "false") << endl;
return 0;
}function canThreePartsEqualSum(arr) {
const totalSum = arr.reduce((acc, val) => acc + val, 0);
if (totalSum % 3 !== 0) return false;
const target = totalSum / 3;
let leftSum = 0, rightSum = 0, i = 0, j = arr.length - 1;
while (i < j) {
if (leftSum !== target) {
leftSum += arr[i++];
}
if (rightSum !== target) {
rightSum += arr[j--];
}
if (leftSum === target && rightSum === target) {
return true;
}
}
return false;
}
// Example usage
const arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4];
console.log(canThreePartsEqualSum(arr)); // Output: true#include <stdbool.h>
#include <stdio.h>
bool canThreePartsEqualSum(int* arr, int arrSize) {
int totalSum = 0;
for (int i = 0; i < arrSize; i++) {
totalSum += arr[i];
}
if (totalSum % 3 != 0) return false;
int target = totalSum / 3, i = 0, j = arrSize - 1;
int leftSum = 0, rightSum = 0;
while (i < j) {
if (leftSum != target) {
leftSum += arr[i++];
}
if (rightSum != target) {
rightSum += arr[j--];
}
if (leftSum == target && rightSum == target) {
return true;
}
}
return false;
}
int main() {
int arr[] = {3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
int size = sizeof(arr) / sizeof(arr[0]);
printf("%s\n", canThreePartsEqualSum(arr, size) ? "true" : "false");
return 0;
}using System;
public class Solution {
public bool CanThreePartsEqualSum(int[] arr) {
int totalSum = 0;
foreach (int num in arr) {
totalSum += num;
}
if (totalSum % 3 != 0) return false;
int target = totalSum / 3;
int leftSum = 0, rightSum = 0, i = 0, j = arr.Length - 1;
while (i < j) {
if (leftSum != target) {
leftSum += arr[i++];
}
if (rightSum != target) {
rightSum += arr[j--];
}
if (leftSum == target && rightSum == target) {
return true;
}
}
return false;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] arr = {3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
Console.WriteLine(solution.CanThreePartsEqualSum(arr) ? "true" : "false");
}
}The Python implementation uses two-pointer technique to validate possible partitions by evaluating sums from outer bounds inward.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Traversal and Summation
First, we calculate the sum of the entire array and check if the sum is divisible by 3. If it is not, we directly return false.
Otherwise, let s represent the sum of each part. We use a variable cnt to record the number of parts found so far, and another variable t to record the current part's sum. Initially, cnt = 0 and t = 0.
Then we traverse the array. For each element x, we add x to t. If t equals s, it means we have found one part, so we increment cnt by one and reset t to 0.
Finally, we check if cnt is greater than or equal to 3.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).
function canThreePartsEqualSum(arr: number[]): boolean {
let s = arr.reduce((a, b) => a + b);
if (s % 3) {
return false;
}
s = (s / 3) | 0;
let [cnt, t] = [0, 0];
for (const x of arr) {
t += x;
if (t == s) {
cnt++;
t = 0;
}
}
return cnt >= 3;
}func canThreePartsEqualSum(arr []int) bool {
s := 0
for _, x := range arr {
s += x
}
if s%3 != 0 {
return false
}
s /= 3
cnt, t := 0, 0
for _, x := range arr {
t += x
if t == s {
cnt++
t = 0
}
}
return cnt >= 3
}impl Solution {
pub fn can_three_parts_equal_sum(arr: Vec<i32>) -> bool {
let sum: i32 = arr.iter().sum();
let s = sum / 3;
let mod_val = sum % 3;
if mod_val != 0 {
return false;
}
let mut cnt = 0;
let mut t = 0;
for &x in &arr {
t += x;
if t == s {
cnt += 1;
t = 0;
}
}
cnt >= 3
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum and Count Approach | Time Complexity: O(n) |
| Two Pointer Approach | Time Complexity: O(n) |
| Traversal and Summation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum and Count | O(n) | O(1) | General case. Simple single pass solution that directly counts valid partitions. |
| Two Pointer Greedy Scan | O(n) | O(1) | When reasoning about explicit partition boundaries or explaining greedy partition logic in interviews. |
Frequently asked questions
Is Partition Array Into Three Parts With Equal Sum easy or hard?
LeetCode classifies this problem as Easy. The main challenge is recognizing that the total sum must be divisible by three and that prefix sums can detect valid partition boundaries in a single pass.
How to solve Partition Array Into Three Parts With Equal Sum in O(n)?
Start by calculating the total sum of the array. If totalSum % 3 != 0, return false. Otherwise set target = totalSum / 3 and iterate through the array while maintaining a running prefix sum. Each time the running sum equals target, reset it and increment a partition counter. If three partitions are formed before the array ends, return true.
What is the best approach for Partition Array Into Three Parts With Equal Sum?
The optimal solution uses a prefix sum scan. First compute the total sum and check if it is divisible by 3. Then iterate through the array and count segments where the running sum equals totalSum / 3. If at least three such segments exist, the partition is possible. This runs in O(n) time with O(1) extra space.
What data structure is used in Partition Array Into Three Parts With Equal Sum?
The solution primarily uses array traversal with prefix sums. No advanced data structures are required. The algorithm keeps a running sum and a counter to detect when segments reach the required target value.
What is the time complexity of Partition Array Into Three Parts With Equal Sum?
The optimal solution runs in O(n) time because the array is scanned once to compute the total sum and once more to identify valid partitions. Space complexity is O(1) since only a few variables are used to track the running sum and segment count.
Partition Array Into Three Parts With Equal Sum Python or Java solution approach?
Both Python and Java implementations follow the same logic: compute the total sum, check divisibility by three, then scan the array while maintaining a running sum. Each time the sum equals target, increment a counter and reset the running sum. If the counter reaches three, the array can be partitioned correctly.
Is Partition Array Into Three Parts With Equal Sum asked at Google, Amazon, or Meta?
This problem appears frequently in coding interview preparation sets and is commonly associated with companies like Amazon and Google in practice platforms. It tests understanding of prefix sums, greedy partitioning, and array traversal in linear time.