Partition Array Into Three Parts With Equal Sum — LeetCode 1013 Python Solution

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] + ...

Example

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

Python solution

class Solution:
    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
        s, mod = divmod(sum(arr), 3)
        if mod:
            return False
        cnt = t = 0
        for x in arr:
            t += x
            if t == s:
                cnt += 1
                t = 0
        return cnt >= 3

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1013. Partition Array Into Three Parts With Equal Sum is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems