[C++/Python] observation leads to solutions & 3-pointer solution
Approach 1:\nTrain of thought [1]:\nStep 1: observation: Find 1st 1 of 3rd sub-array\nStep 2: locate the ending of 1st and 2nd sub-arrays\n\nTime Complexity: O(
Approach 1:\nTrain of thought [1]:\nStep 1: observation: Find 1st 1 of 3rd sub-array\nStep 2: locate the ending of 1st and 2nd sub-arrays\n\nTime Complexity: O(N)\nSpace Complexity: O(1)\n\n```\nclass Solution {\npublic:\n    vector<int> threeEqualParts(vector<int>& A) {\n        int tot = 0;\n        for(auto num: A) tot += num;\n        if(tot % 3 != 0) return {-1, -1};\n        int n = A.size();\n        if(tot == 0) return {0, n - 1};\n        \n        int seg3_beg_candidate = n - 1;\n        for(int i = n - 1, cnt = 0; i >= 0; i--){\n            if(A[i]==1){\n                cnt++;\n                if(cnt == tot / 3){\n                    seg3_beg_candidate = i;\n                    break;\n                }\n            }\n        }\n        \n        int seg1_end = findSegEnd(A, 0, seg3_beg_candidate);\n        if(seg1_end == -1) return {-1, -1};\n        int seg2_end = findSegEnd(A, seg1_end + 1, seg3_beg_candidate);\n        if(seg2_end == -1) return {-1, -1};\n        else return {seg1_end, seg2_end + 1};\n    }\n    \nprivate:\n    int findSegEnd(const vector<int>& A, int l, int r){\n        while(A[l] == 0) l++;\n        while(r < A.size()){\n            if(A[l] != A[r]) return -1;\n            l++; r++;\n        }\n        return l - 1;\n    }\n};\n```\n\nApproach 2: 3-pointer [2]\nThis might be the only 3-pointer type question out of  1009 questions solved by me.\nThe solution is from [2] with clear step by step illustration.\n```\nstatic int x=[](){ios::sync_with_stdio(false); cin.tie(NULL); return 0;}();\n\nclass Solution {\npublic:\n    vector<int> threeEqualParts(vector<int>& A) {\n\t    // Count no of 1\'s in the given array\n        int countNumberOfOnes = 0;\n        for(int c: A)\n            if(c == 1)                  \n                countNumberOfOnes++;\n\t\t\t\t\t\t\t\t\n\t    // If no 1 is found, that means we can return ans as {0, size-1}\n\t\tint n = A.size();\n        if(countNumberOfOnes == 0)      \n            return {0, n -1};\n\t\t\t\t\t\t\n        // If no of 1\'s is not a multiple of 3, then we can never find a possible partition since\n        // there will be atkeast one partition that will have different no of 1\'s and hence\n        // different binary representation\n        // For example,\n        // Given :\n        // 0000110  110  110 \n        //       |  |    |\n        //       i       j\n        // Total no of ones = 6\n        // 0000110         110      110\n        //     |           |        |\n        //     start       mid      end\n        // Match starting from first 1, and putting 2 more pointers by skipping k 1\'s\n        \n        if(countNumberOfOnes % 3 != 0)            \n            return {-1, -1};\n\t\t\t\t\t\t\n        // find size of each partition\n        int k = countNumberOfOnes/3;\n        int i;\n        \n        // find the first 1 in the array\n        for(i=0;i<A.size(); i++)\n            if(A[i] == 1)\n                break;\n        int start = i;\n        \n        // find (k+1)th 1 in the array\n        int count1 = 0;\n        for(i=0;i<A.size(); i++)\n        {\n            if(A[i] == 1)\n                count1++;\n            if(count1 == k + 1)\n                break;\n        }\n        int mid = i;\n        \n        //find (2*k +1)th 1 in the array\n        count1= 0;\n        for(i=0;i<A.size(); i++)\n        {\n            if(A[i] == 1)\n                count1++;\n            if(count1 == 2*k + 1)\n                break;\n        }\n        int end = i;\n        \n        // Match all values till the end of the array\n        while(end< A.size() && A[start] == A[mid] && A[mid] == A[end])\n        {\n            start++; mid++; end++;\n        }\n        \n        // Return appropriate values if all the values have matched till the end\n        if(end == A.size()) \n            return {start-1, mid};\n        \n        // otherwise, no such indices found\n        return {-1, -1};\n    }\n};\n```\n\nApproach 3: Compact version of Approach 2\n```\nclass Solution {\npublic:\n    vector<int> threeEqualParts(vector<int>& A) {\n\t    // Count no of 1\'s in the given array\n        int countNumberOfOnes = 0;\n        int n = A.size();\n        for(int c: A)\n            if(c == 1)                  \n                countNumberOfOnes++;\n\t\t\t\t\t\t\t\t\n\t    // If no 1 is found, that means we can return ans as {0, size-1}\n        if(countNumberOfOnes == 0)      \n            return {0, n -1};\n\t\t\t\t\t\t\n        // If no of 1\'s is not a multiple of 3, then we can never find a possible partition since\n        // there will be atkeast one partition that will have different no of 1\'s and hence\n        // different binary representation\n        // For example,\n        // Given :\n        // 0000110  110  110 \n        //       |  |    |\n        //       i       j\n        // Total no of ones = 6\n        // 0000110         110      110\n        //     |           |        |\n        //     start       mid      end\n        // Match starting from first 1, and putting 2 more pointers by skipping k 1\'s\n        \n        if(countNumberOfOnes % 3 != 0)            \n            return {-1, -1};\n\t\t\t\t\t\t\n        // find size of each partition\n        int k = countNumberOfOnes/3;\n        int i;\n        \n        // start: the first 1 in the array\n        // mid:   the (k+1)th 1 in the array\n        // end:   the (2k+1)th 1 in the array\n        int oneIdx = 0;\n        int start, mid, end;\n        for(i=0;i<A.size(); i++)\n            if(A[i] == 1){\n                ++oneIdx;\n                if( oneIdx == 1) start = i;\n                if( oneIdx == k + 1) mid = i;\n                if( oneIdx == 2*k + 1) {end = i;break;}\n            }\n        \n        // Match all values till the end of the array\n        while(end< A.size() && A[start] == A[mid] && A[mid] == A[end]){\n            start++; mid++; end++;\n        }\n        \n        // Return appropriate values if all the values have matched till the end\n        if(end == A.size()) \n            return {start-1, mid};\n        \n        // otherwise, no such indices found\n        return {-1, -1};\n    }\n};\n```\n\nApproach 4: 8-line python [3]\n```\ndef threeEqualParts(self, nums: List[int]) -> List[int]:\n\tn = nums.count(1)\n\tif n == 0: return [0, 2] # any split would satify\n\tif n % 3 != 0: return [-1, -1]\n\tidx = [i for i, num in enumerate(nums) if num == 1]\n\ts1, e1, s2, e2, s3, e3 = idx[0], idx[n//3-1], idx[n//3], idx[2*n//3-1], idx[2*n//3], idx[n-1]\n\ttracingZeros = len(nums) - 1 - e3\n\tif e1 + tracingZeros >= s2 or e2 + tracingZeros >= s3 or not nums[s1: e1] == nums[s2: e2] == nums[s3: e3]: return [-1, -1]\n\treturn [e1 + tracingZeros, e2 + tracingZeros + 1]\n\n```\nReference:\n[1] https://www.cnblogs.com/grandyang/p/12107091.html\n[2] https://leetcode.com/problems/three-equal-parts/discuss/183922/C%2B%2B-O(n)-time-O(1)-space-12-ms-with-explanation-and-comments\n[3] https://leetcode.com/problems/three-equal-parts/discuss/677626/Python-O(n)-Straightforward-Solution\n
['C', 'Python']