LeetCode 1013: Partition Array Into Three Parts With Equal Sum

Problem Restatement

We are given an integer array arr.

We need to return true if we can partition the array into three non-empty contiguous parts that each have the same sum.

Formally, find indices i and j such that:

0 < i < j < len(arr)
sum(arr[:i]) == sum(arr[i:j]) == sum(arr[j:])

If such indices exist, return true. Otherwise return false.

The official constraints state that 3 <= arr.length <= 5 * 10^4 and -10^4 <= arr[i] <= 10^4.

Input and Output

Function shape:

def canThreePartsEqualSum(arr: list[int]) -> bool:
    ...

Examples

Example 1:

arr = [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]

Total sum is 9. Each part should sum to 3.

Partition: [0,2,1], [-6,6,-7,9,1], [2,0,1] → sums 3, 3, 3. ✓

Answer:

True

Example 2:

arr = [0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1]

Total sum is 21. Each part should sum to 7.

But no such partition exists.

Answer:

False

Key Insight

The total sum must be divisible by 3. Each part must equal total / 3.

Scan the array while accumulating a running sum. Each time the running sum hits target, we have found one part boundary. After finding two boundaries, check if a third non-empty part remains.

Algorithm

1. Compute total = sum(arr). If total % 3 != 0, return False.
2. Set target = total // 3.
3. Scan the array, tracking the running sum and the count of parts found.
4. When the running sum equals target * parts_found, increment the parts count.
5. If we found 3 parts and there are elements remaining, return True (but ensure the third part is non-empty by requiring the boundary to be before the last element).

Simpler: scan for the first boundary, then the second boundary, then check elements remain.

Correctness

If total is not divisible by 3, no equal-sum partition exists.

If it is, we greedily find the earliest position where the prefix sum equals target. Then from there, find the next position where the cumulative sum equals 2 * target. If this second boundary is before the last element, the third part exists and is non-empty.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def canThreePartsEqualSum(self, arr: list[int]) -> bool:
        total = sum(arr)
        if total % 3 != 0:
            return False

        target = total // 3
        parts = 0
        running = 0

        for i in range(len(arr)):
            running += arr[i]
            if running == target * (parts + 1):
                parts += 1
            if parts == 2 and i < len(arr) - 1:
                return True

        return False

Code Explanation

Check divisibility:

if total % 3 != 0:
    return False

Scan while counting part boundaries:

running += arr[i]
if running == target * (parts + 1):
    parts += 1

After finding the second boundary, check that we are not at the last element (ensuring the third part is non-empty):

if parts == 2 and i < len(arr) - 1:
    return True

Testing

def run_tests():
    s = Solution()

    assert s.canThreePartsEqualSum([0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]) == True
    assert s.canThreePartsEqualSum([0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1]) == False
    assert s.canThreePartsEqualSum([3, 3, 6, 5, -2, 2, 5, 1, -9, 4]) == True
    assert s.canThreePartsEqualSum([1, 1, 1]) == True
    assert s.canThreePartsEqualSum([0, 0, 0, 0]) == True

    print("all tests passed")

run_tests()