Three Equal Parts | Easiest Approach | O(N) Time complexity and O(1) Space Complexity |
Intuition\nThe problem requires us to divide an array of zeros and ones into three parts, each representing the same binary value. At first glance, it might see
# Intuition\nThe problem requires us to divide an array of zeros and ones into three parts, each representing the same binary value. At first glance, it might seem complex, but by breaking it down into steps, we can solve it systematically. The key insight is to ensure that the count of 1s in each part is equal, which ensures the binary values are identical.\n\n# Approach\n1) Count the total number of 1s in the array. If this number is not divisible by 3, return [-1, -1] as it\'s impossible to split them equally.\n2) Identify the target number of 1s in each part (which will be one-third of the total count of 1s).\n3) Locate the positions of the first, middle, and last groups of 1s that would mark the boundaries of the three parts.\n4) Extract and compare the three parts to ensure they are equal.\n5) Adjust for trailing zeros in each part to ensure valid partition indices.\n\n# Complexity\n- Time complexity:\nO(n) - We traverse the array a few times for counting and extracting parts.\n\n- Space complexity:\nO(1) - We use a constant amount of extra space, not counting the input and output.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> threeEqualParts(vector<int>& arr) {\n        int cnt = 0;\n        for(int i = 0 ; i < arr.size() ; i++) if(arr[i] == 1) cnt++;\n        if(cnt % 3 != 0) return {-1, -1};\n        if(cnt == 0) return {0, 2};\n\n        int k = cnt / 3, curr = 0;\n        int i1 = -1, i2 = -1, i3 = -1;\n        int j1 = -1, j2 = -1, j3 = -1;\n\n        for(int i = 0 ; i < arr.size() ; i++)\n        {\n            if(arr[i] == 1)\n            {\n                curr++;\n                if(curr == 1) i1 = i;\n                if(curr == k + 1) i2 = i;\n                if(curr == 2*k + 1) i3 = i;\n\n                if(curr == k) j1 = i;\n                if(curr == 2*k) j2 = i;\n                if(curr == 3*k) j3 = i;\n            }\n        }\n        vector < int > a, b, c;\n        copy(arr.begin() + i1, arr.begin() + j1 + 1, back_inserter(a));\n        copy(arr.begin() + i2, arr.begin() + j2 + 1, back_inserter(b));\n        copy(arr.begin() + i3, arr.begin() + j3 + 1, back_inserter(c));\n\n        if(a != b || a != c) return {-1, -1};\n\n        int first = 0, second = 0, third = 0;\n        first = i2 - j1 - 1;\n        second = i3 - j2 - 1;\n        third = arr.size() - j3 - 1;\n\n        if(third > min(first, second)) return {-1, -1};\n        \n        return {j1 + third, j2 + third + 1};\n    }\n};\n```\n\n\n# **Bold**
['Array', 'Math', 'Two Pointers', 'Greedy', 'C++']