python O(n) beat 100% 304ms
\nclass Solution(object):\n    def threeEqualParts(self, arr):\n        N = len(arr)\n        \n        # ones_number : number of \'1\' in arr\n        ones_num
```\nclass Solution(object):\n    def threeEqualParts(self, arr):\n        N = len(arr)\n        \n        # ones_number : number of \'1\' in arr\n        ones_number = sum(arr)\n        if ones_number % 3 != 0: return [-1,-1]\n        if ones_number == 0: return [0,N-1]\n        \n        # ones_each : number of \'1\' in one part\n        ones_each = ones_number // 3\n        \n        # ones_idx : idx of \'1\', divided in 3 parts\n        ones_idx, tmp, count = [], [], 0\n        for i in range(len(arr)):\n            if arr[i] == 1:\n                tmp += [i]\n                count += 1\n            \n            if count == ones_each:\n                ones_idx.append(tmp)\n                tmp = []\n                count = 0\n        \n        # ones_idx_shift : idx of \'1\', divided in 3 parts, but each subarr is shifted to start with one\n\t\t# used for comparing the pattern\n        ones_idx_shift = []\n        for ls in ones_idx:\n            ones_idx_shift.append([ls[i] - ls[0] for i in range(ones_each)])\n        \n        # zeros_tail : numbers of \'0\' behind the last \'1\'\n        zeros_tail = N - ones_idx[2][-1] -1\n        \n        # Rule 1: Space for zero\n        # no space for zeros for part1 and part2\n        if ones_idx[1][0] - ones_idx[0][-1] -1 < zeros_tail or ones_idx[2][0] - ones_idx[1][-1] -1 < zeros_tail:\n            return [-1,-1]\n        \n        # Rule 2: Pattern of three parts\n        # compare the pattern of part1, part2, and part3\n        if ones_idx_shift[0] == ones_idx_shift[1] and ones_idx_shift[1] == ones_idx_shift[2]:\n            return [ones_idx[0][-1] + zeros_tail, ones_idx[1][-1] +1 + zeros_tail]\n        \n        return [-1,-1]\n```\n### Sum of arr needs to be 3n\nSince the arr is divided into 3 equal parts, the number of \'1\' need to be the multiple of 3.\n\n\n### Need to match two rule\n\n#### Rule 1: Space for zero\nWe need to make sure that there are enough \'0\' between each part.\n\nBecause **the \'0\' behind the last \'1\' is used in part3 for sure**, we can count whether there are enough \'0\' between (part1 ,part2) and between (part2, part3), which meen more than the number of \'0\' behind the last \'1\'.\n\n#### Rule 2: Pattern of three parts\nPattern of three parts need to be the same.\n\nWe divide arr based on the number of \'1\', each part only have 1/3 number of \'1\'.\n\nFor example:\n[1, 0, 0, 1, 0, 1, 0] can be divided into [1,0], [1,0], [1,0] => same\n[1, 1, 0, 1, 0, 1, 1, 0, 0, 1] can be divided into [1, 1, 0], [1, 0, 1], [1, 0, 0, 1] => not the same
[]