LeetCode 1013 - Partition Array Into Three Parts With Equal Sum

Difficulty: 🟢 Easy
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives us an integer array arr and asks whether it can be divided into exactly three non-empty contiguous parts such that all three parts have the same sum.

The partitions must preserve the original order of the array. We are not allowed to rearrange elements. Instead, we choose two cut positions that split the array into:

Part 1: arr[0...i]
Part 2: arr[i+1...j-1]
Part 3: arr[j...n-1]

The problem requires:

Every part must contain at least one element
The sums of the three parts must all be equal

If such a partition exists, we return true. Otherwise, we return false.

The key observation is that if the total sum of the array is not divisible by 3, then it is impossible for three equal-sum partitions to exist. Each partition must contribute exactly one third of the total sum.

The constraints are:

3 <= arr.length <= 5 * 10^4
-10^4 <= arr[i] <= 10^4

The array can contain negative numbers, zeros, and positive numbers. Because the input size can reach fifty thousand elements, inefficient approaches such as checking every possible pair of partition boundaries would be too slow.

Several edge cases are important:

Arrays whose total sum is not divisible by 3
Arrays containing many zeros
Arrays with negative numbers that can cause sums to fluctuate
Cases where equal partial sums appear early, but the remaining portion is empty
Arrays where multiple valid partitions exist

The problem guarantees that the array length is at least 3, so forming three non-empty parts is at least structurally possible.

Approaches

Brute Force Approach

A straightforward solution is to try every possible pair of partition indices.

We choose:

First cut after index i
Second cut before index j

Then we compute:

Sum of arr[0...i]
Sum of arr[i+1...j-1]
Sum of arr[j...n-1]

If all three sums are equal for any pair (i, j), we return true.

This approach is correct because it explicitly checks every valid partition configuration. However, it is inefficient.

There are O(n^2) possible partition pairs. If we compute sums naively for every partition, the complexity becomes O(n^3). Even with prefix sums, it still requires O(n^2) checks, which is too slow for n = 5 * 10^4.

Optimal Greedy Approach

The important insight is that we do not actually need to test every partition boundary.

Suppose the total sum is S.

If the array can be partitioned into three equal parts, then each part must sum to:

$$\frac{S}{3}$$

So the problem becomes:

Can we find one prefix with sum target
Then another prefix later with sum target
Leaving at least one element for the final partition

We scan the array once while maintaining a running sum.

Whenever the running sum becomes equal to target, we count one partition and reset the running sum to zero. If we can form at least three such partitions, then the answer is true.

The greedy strategy works because contiguous partitions are formed naturally during the left-to-right traversal.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Tries every possible partition pair
Optimal	O(n)	O(1)	Single pass greedy accumulation

Algorithm Walkthrough

Compute the total sum of the array.

We first calculate the sum of all elements. If the total sum is not divisible by 3, then three equal partitions are impossible, so we immediately return false. 2. Compute the target partition sum.

Each partition must have sum:

$$target = \frac{total}{3}$$ 3. Initialize variables.

We maintain:

current_sum, the running sum of the current partition
partitions_found, the number of partitions whose sum equals target

Traverse the array from left to right.

For each number:

Add it to current_sum
If current_sum == target:
Increment partitions_found
Reset current_sum to 0

Check whether at least three partitions were found.

If we can form at least three contiguous segments with sum target, then the array can be partitioned correctly.

Otherwise, return false.

Why it works

The algorithm relies on the fact that the total array sum equals 3 * target. Therefore, whenever we identify two earlier contiguous partitions with sum target, the remaining elements must also sum to target.

The greedy scan never misses a valid solution because partitions are formed in order, and contiguous boundaries are preserved naturally during traversal.

Python Solution

from typing import List

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total_sum = sum(arr)

        if total_sum % 3 != 0:
            return False

        target = total_sum // 3

        current_sum = 0
        partitions_found = 0

        for num in arr:
            current_sum += num

            if current_sum == target:
                partitions_found += 1
                current_sum = 0

        return partitions_found >= 3

The implementation begins by calculating the total sum of the array. If the sum is not divisible by 3, the function immediately returns False because equal partitions are mathematically impossible.

Next, we compute the required sum for each partition using integer division.

The algorithm then performs a single traversal through the array. The variable current_sum accumulates the values of the current segment. Whenever the running sum reaches the target value, we treat that segment as one completed partition.

After finding such a partition, we reset the running sum so that accumulation for the next partition starts fresh.

Finally, if at least three valid partitions were discovered, we return True.

The implementation does not explicitly track partition indices because the greedy accumulation already guarantees contiguous segments.

Go Solution

func canThreePartsEqualSum(arr []int) bool {
    totalSum := 0

    for _, num := range arr {
        totalSum += num
    }

    if totalSum%3 != 0 {
        return false
    }

    target := totalSum / 3

    currentSum := 0
    partitionsFound := 0

    for _, num := range arr {
        currentSum += num

        if currentSum == target {
            partitionsFound++
            currentSum = 0
        }
    }

    return partitionsFound >= 3
}

The Go implementation follows the same logic as the Python version.

Go slices are used directly for traversal. Integer arithmetic is safe here because the constraints are small enough that overflow is not a concern with Go's standard int type.

Unlike Python, Go does not provide a built-in sum() function, so the total sum is computed manually with a loop.

Worked Examples

Example 1

Input: [0,2,1,-6,6,-7,9,1,2,0,1]

Total sum:

0 + 2 + 1 - 6 + 6 - 7 + 9 + 1 + 2 + 0 + 1 = 3

Target partition sum:

3 / 3 = 1

Index	Value	Running Sum
0	0	0
1	2	2
2	1	3
3	-6	-3
4	6	3
5	-7	-4
6	9	5
7	1	6
8	2	8
9	0	8
10	1	9

The above table shows raw accumulation, but the greedy reset behavior is the actual execution:

Index	Value	Running Sum After Add	Action
0	0	0	continue
1	2	2	continue
2	1	3	continue
3	-6	-3	continue
4	6	3	continue
5	-7	-4	continue
6	9	5	continue
7	1	6	continue
8	2	8	continue
9	0	8	continue
10	1	9	continue

This raw table does not isolate partitions correctly because the target is actually:

$$3 / 3 = 1$$

So the proper traversal is:

Index	Value	Running Sum
0	0	0
1	2	2
2	1	3
3	-6	-3
4	6	3
5	-7	-4
6	9	5
7	1	6
8	2	8
9	0	8
10	1	9

The correct partitioning interpretation is:

[0,2,1] has sum 3
[-6,6,-7,9,1] has sum 3
[2,0,1] has sum 3

Since three equal partitions exist, the answer is true.

Example 2

Input: [0,2,1,-6,6,7,9,-1,2,0,1]

Total sum:

Since:

$$21 \bmod 3 = 0$$

the target is:

$$7$$

During traversal, we cannot form three valid contiguous partitions with sum 7.

Therefore, the answer is false.

Example 3

Input: [3,3,6,5,-2,2,5,1,-9,4]

Total sum:

Target:

Traversal:

Index	Value	Running Sum	Partitions Found
0	3	3	0
1	3	6	1
2	6	6	2
3	5	5	2
4	-2	3	2
5	2	5	2
6	5	10	2
7	1	11	2
8	-9	2	2
9	4	6	3

Three partitions are found, so the answer is true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single traversal through the array
Space	O(1)	Only a few variables are used

The algorithm performs one pass to compute the total sum and another pass to identify partitions. Since both passes are linear, the overall complexity remains O(n).

No auxiliary data structures proportional to input size are required, so the space usage is constant.

Test Cases

from typing import List

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        total_sum = sum(arr)

        if total_sum % 3 != 0:
            return False

        target = total_sum // 3

        current_sum = 0
        partitions_found = 0

        for num in arr:
            current_sum += num

            if current_sum == target:
                partitions_found += 1
                current_sum = 0

        return partitions_found >= 3

sol = Solution()

assert sol.canThreePartsEqualSum([0,2,1,-6,6,-7,9,1,2,0,1]) == True
# standard valid example

assert sol.canThreePartsEqualSum([0,2,1,-6,6,7,9,-1,2,0,1]) == False
# standard invalid example

assert sol.canThreePartsEqualSum([3,3,6,5,-2,2,5,1,-9,4]) == True
# valid partition with negatives

assert sol.canThreePartsEqualSum([0,0,0]) == True
# all zeros

assert sol.canThreePartsEqualSum([1,-1,1,-1,1,-1]) == True
# alternating values

assert sol.canThreePartsEqualSum([1,2,3,4]) == False
# total sum not divisible by 3

assert sol.canThreePartsEqualSum([1,1,1]) == True
# minimum valid size

assert sol.canThreePartsEqualSum([1,2,-3,3]) == False
# cannot form three non-empty equal parts

assert sol.canThreePartsEqualSum([-1,-1,-1,-1,-1,-1]) == True
# all negative numbers

assert sol.canThreePartsEqualSum([10,-10,10,-10,10,-10]) == True
# repeated cancellation pattern

Test Summary

Test	Why
`[0,2,1,-6,6,-7,9,1,2,0,1]`	Standard valid example
`[0,2,1,-6,6,7,9,-1,2,0,1]`	Standard invalid example
`[3,3,6,5,-2,2,5,1,-9,4]`	Valid partition with mixed signs
`[0,0,0]`	All-zero edge case
`[1,-1,1,-1,1,-1]`	Frequent sum resets
`[1,2,3,4]`	Sum not divisible by three
`[1,1,1]`	Smallest valid array
`[1,2,-3,3]`	Insufficient partition structure
`[-1,-1,-1,-1,-1,-1]`	Entirely negative values
`[10,-10,10,-10,10,-10]`	Alternating cancellation behavior

Edge Cases

One important edge case is when the total sum is not divisible by 3. In such situations, equal partitions are mathematically impossible. A buggy implementation might still attempt partition scanning and incorrectly return true. The implementation avoids this by performing an early divisibility check.

Another important case is arrays containing all zeros, such as [0,0,0]. The target partition sum becomes zero, which means every prefix may appear valid. Some implementations incorrectly stop after finding two partitions. Our implementation correctly counts partitions greedily and verifies that at least three valid segments exist.

Negative numbers also create subtle behavior because running sums can increase and decrease unpredictably. For example, a prefix may overshoot the target and later return to it. A simplistic two-pointer approach would fail here. The greedy running-sum accumulation handles negative values naturally because it only checks whether the current contiguous segment equals the target sum.

A final subtle edge case involves ensuring partitions are non-empty. Suppose we find two valid partitions too early and leave no elements for the third partition. Because the algorithm only counts completed contiguous segments during traversal, the final partition must contain actual elements from the remaining suffix. This naturally enforces the non-empty requirement.