Watch 10 video solutions for Partition Array Into Three Parts With Equal Sum, a easy level problem involving Array, Greedy. This walkthrough by Ren Zhang has 3,323 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 104Problem 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 | 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. |