Partition Array Into Three Parts With Equal Sum - Solution & Explanation
Problem Statement
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.
This C implementation iterates over the array while maintaining a running sum and a count of partitions where the running sum matches the target. If there are three or more partitions by the end, it returns true.
Complexity
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since we are using a constant amount of extra space.
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.
This C implementation uses two pointers from opposite ends of the array to find two sections of the target sum, which implies that the middle is also a valid partition.
Complexity
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).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix Sum and Count Approach | Time Complexity: O(n), where n is the length of the array. |
| Two Pointer Approach | Time Complexity: O(n) |
| Traversal and Summation | — |
Detailed 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. |
Video Solution
Leetcode 1013 Partition Array Into Three Parts With Equal Sum • Ren Zhang • 3,351 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Partition Array Into Three Parts With Equal Sum easy or hard?
How to solve Partition Array Into Three Parts With Equal Sum in O(n)?
What is the best approach for Partition Array Into Three Parts With Equal Sum?
What data structure is used in Partition Array Into Three Parts With Equal Sum?
What is the time complexity of Partition Array Into Three Parts With Equal Sum?
Partition Array Into Three Parts With Equal Sum Python or Java solution approach?
Is Partition Array Into Three Parts With Equal Sum asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Partition Array Into Three Parts With Equal Sum with our built-in code editor and test cases.
Practice on FleetCode