Three Equal Parts — LeetCode 927 Python Solution

The problem

You are given an array arr which consists of only zeros and ones, divide the array into three non-empty parts such that all of these parts represent the same binary value. If it is possible, return any [i, j] with i + 1 < j, such that: arr[0], arr[1], ..., arr[i] is the first part, arr[i + 1], arr[i + 2], ..., arr[j - 1] is the second part, and arr[j], arr[j + 1], ..., arr[arr.length - 1] is the third part.

Example

Input

arr = [1,0,1,0,1]

Output

[0,3]

Python solution

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        def find(x):
            s = 0
            for i, v in enumerate(arr):
                s += v
                if s == x:
                    return i

        n = len(arr)
        cnt, mod = divmod(sum(arr), 3)
        if mod:
            return [-1, -1]
        if cnt == 0:
            return [0, n - 1]

        i, j, k = find(1), find(cnt + 1), find(cnt * 2 + 1)
        while k < n and arr[i] == arr[j] == arr[k]:
            i, j, k = i + 1, j + 1, k + 1
        return [i - 1, j] if k == n else [-1, -1]

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 927. Three Equal Parts is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems