927. Three Equal Parts (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def threeEqualParts(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        # count 1s
        s = sum(arr)
        if not s:
            return [0, 2]
        if s % 3:
            return [-1, -1]
        s1 = s2 = s3 = 0
        count = 0
        for i, num in enumerate(arr):
            if num:
                if count == 0:
                    s1 = i
                elif count == s // 3:
                    s2 = i
                elif count == s // 3 * 2:
                    s3 = i
                    break
                count += 1
        n = len(arr) - s3
        if arr[s1 : s1 + n] == arr[s2 : s2 + n] == arr[s3 : ]:
            return [s1 + n - 1, s2 + n]
        return [-1, -1]
        
        # brute force two pointers
        k = 0
        while k < len(arr) and arr[k] == 0:
            k += 1
        s = "".join([str(x) for x in arr[k : ]])
        if not s:
            return [0, 2]
        i, j = 0, len(s)
        s1 = s2 = r = ""
        while i < j:
            if s1 == r == s[j - i : j] and "1" not in s[i : j - i]:
                return [i - 1 + k, j + k]
            if len(s1) >= len(r):
                j -= 1
                s2 = s[j] + s2
                if s[j] == "1":
                    r = s2
            else:
                s1 += s[i]
                i += 1
        return [-1, -1]