[C++] Single Pass Solution Explained, ~100% Time, ~90% Space
Nice problem that becomes much easier once you figure out a few tricks:\n first of all, in order for the problem to be solvable, we need an amount of 1s divisib
Nice problem that becomes much easier once you figure out a few tricks:\n* first of all, in order for the problem to be solvable, we need an amount of `1`s divisible by `3`;\n* with this insight, we can figure out that while we move on checking for the amount of `1`s, we might as well keep track of pointers separating the currently explored portion of the array into `3` parts;\n* to get this pointer in place, we might think of doing something similar to navigating a linked list with the hare-tortoise approach, just this time we would have `3` pointers (`s1`, `s2` and `i`, later in my code), proceeding at 1X, 2X and 3X speed respectively.\n\nFor example, if we started with `{0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0}`, we would initially find all 3 pointers set when we meet the third `1`, so, it would be:\n\n```cpp\ns1 == 1;  // position of the first 1\ns2 == 2;  // position of the second 1\n i == 5;  // position of the third 1\n```\n\nOnce we met the sixth `1` we have:\n\n```cpp\ns1 == 2;  // position of the second 1\ns2 == 6;  // position of  the fourth 1\n i == 13; // position of the sixth 1\n```\n\nAnd so on; with that in mind, then it becomes much easier to figure out the limits of a partition (the position of the last one will dictate the padding `0`s to all the others) and we can proceed from that.\n\nIn order to code it, we will use a few support variables:\n* `tot` is out ongoing total, initialised to `0`;\n* `lastElem` is the position of the last element, initialised to be `arr.size()` (for now, we will fix it in a moment!);\n* `lmt` gives us the upper limit of how many positions for either `s1` or `s2` we are going to store, initalised to be `lastElem / 3` (ie: we will never have more positions than one third of the length, if even if all elements were to be `1`s);\n* `s1`, `s2` and `last` will keep track of where we found the delimiting `1`s for each session discovered so far;\n* `curr1` and `curr2` will be the positions of the `s1` and `s2` pointers we will be using, both set to `0` initially;\n* `pos1` and `pos2`, specularly, will point to where we are going to store them in their respective arrays;\n* `s1s` and `s2s` are the arrays that will store pointers to our dividing points as we go.\n\nDone with the variables, we can now fix `lastElem` to correctly be the index of the last element and loop with `i` through `arr`, and:\n* we will check if the currenlty pointed element `arr[i]` is  a `1` and, if so:\n\t* increase `tot` by `1`;\n\t* store the current position in `s1s`, provided we did not do so already for `lmt` elements;\n\t* store the current position in `s2s`, provided we did not do so already for `lmt` elements and that we parsed so far an even number of `1`s;\n\t* it `tot` is divisible by `3`, we will then:\n\t\t* update the `last`, `s1` and `s2` pointers to new values.\n\nWith this out of the way, time to parse for a few edge cases:\n * if no `1`s were found (ie: `!tot`), we will then just `return` `{0, lastElem}` (I think why not any other pointer for the second element was not very clear in the description, but okay);\n * if `tot` is not divisible by `3`, clearly we cannot form `3` parts with the same amount of `1`s, so we will `return` `{-1, -1}`.\n \nOne last condition to check is that the sections have exactly the same binary value and this is a bit trickier.\n \nTo do so, we will use a new variable `diff` computed as the difference between `last` and `lastElem` to get the amount of necessary padding `0`s.\n \n We will then:\n * increase `s1` by `diff` and check if it is still below `s2`, otherwise we will `return` `{-1, -1}`;\n * increase `s2` by `diff` and check if it is still below `last`, otherwise we will `return` `{-1, -1}`;\n * set `curr1` to be `s1`, `curr2` to be `s2`, `last` to `lastElem` and `tot` to one third of its original value;\n * we will loop while `tot > 0` and:\n\t * check if `curr1`, `curr2` and `last` point to the same value (either all point to a `0` or to a `1`), otherwise `return` `{-1, -1}`;\n\t * reduce `tot` by the currently pointed value by any of the pointers;\n\t * decrease all three pointers by `1`.\n\nYou might notice that even if any of the sections still had leading `0`s, in this way we would not care, stopping at the last `1` of each session - assuming no mismatch was detected earlier.\n\nOnce done, we can `return` `{s1, s2 + 1}` (remember that the second pointer is requested to be where the last segment starts) and be done :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    vector<int> threeEqualParts(vector<int>& arr) {\n        int tot = 0, lastElem = arr.size(), lmt = lastElem / 3, s1, s2, last,\n        curr1 = 0, curr2 = 0, pos1 = 0, pos2 = 0, s1s[lmt], s2s[lmt];\n        lastElem--;\n        for (int i = 0; i <= lastElem; i++) {\n            // finding a `1`\n            if (arr[i]) {\n                tot++;\n                // storing i in s1s if it is not full\n                if (pos1 < lmt) s1s[pos1++] = i;\n                // storing i in s2s every 2 1s if it is not full\n                if (pos2 < lmt && !(tot & 1)) s2s[pos2++] = i;\n                // updating pointers every 3 1s\n                if (!(tot % 3)) {\n                    last = i;\n                    s1 = s1s[curr1++];\n                    s2 = s2s[curr2++];\n                }\n            }\n        }\n        // edge case: no 1s\n        if (!tot) return {0, lastElem};\n        // exit case: can\'t form 3 groups with the same number of 1s\n        if (tot % 3) return {-1, -1};\n        // moving the pointer to the last 0 of the sequence\n        int diff = lastElem - last;\n        // updating s1 and s2, plus exit case: not enough 0s between either s1 and s2 or s2 and last\n        s1 += diff;\n        if (s1 >= s2) return {-1, -1};\n        s2 += diff;\n        if (s2 >= last) return {-1, -1};\n        // updating curr1, curr2, last and tot to check the segment structure\n        curr1 = s1, curr2 = s2, last = lastElem, tot /= 3;\n        while (tot) {\n            // checking if all the elements match\n            if (arr[curr1] != arr[curr2] || arr[curr2] != arr[last]) return {-1, -1};\n            // updating variables for the next loop\n            tot -= arr[curr1];\n            curr1--, curr2--, last--;\n        }\n        // checking if the segments have the same structure\n        return {s1, s2 + 1};\n    }\n};\n```\nMicro-optimisation, declaring and assigning `s1` and `s2` at the end and if it might be a proper solution:\n\n```cpp\nclass Solution {\npublic:\n    vector<int> threeEqualParts(vector<int>& arr) {\n        int tot = 0, lastElem = arr.size(), lmt = lastElem / 3, last,\n        curr1 = -1, curr2 = -1, pos1 = 0, pos2 = 0, s1s[lmt], s2s[lmt];\n        lastElem--;\n        for (int i = 0; i <= lastElem; i++) {\n            // finding a `1`\n            if (arr[i]) {\n                tot++;\n                // storing i in s1s if it is not full\n                if (pos1 < lmt) s1s[pos1++] = i;\n                // storing i in s2s every 2 1s if it is not full\n                if (pos2 < lmt && !(tot & 1)) s2s[pos2++] = i;\n                // updating pointers every 3 1s\n                if (!(tot % 3)) {\n                    last = i;\n                    curr1++;\n                    curr2++;\n                }\n            }\n        }\n        // edge case: no 1s\n        if (!tot) return {0, lastElem};\n        // exit case: can\'t form 3 groups with the same number of 1s\n        if (tot % 3) return {-1, -1};\n        // moving the pointer to the last 0 of the sequence\n        int diff = lastElem - last, s1 = s1s[curr1], s2 = s2s[curr2];\n        // updating s1 and s2, plus exit case: not enough 0s between either s1 and s2 or s2 and last\n        s1 += diff;\n        if (s1 >= s2) return {-1, -1};\n        s2 += diff;\n        if (s2 >= last) return {-1, -1};\n        // updating curr1, curr2, last and tot to check the segment structure\n        curr1 = s1, curr2 = s2, last = lastElem, tot /= 3;\n        while (tot) {\n            // checking if all the elements match\n            if (arr[curr1] != arr[curr2] || arr[curr2] != arr[last]) return {-1, -1};\n            // updating variables for the next loop\n            tot -= arr[curr1];\n            curr1--, curr2--, last--;\n        }\n        // checking if the segments have the same structure\n        return {s1, s2 + 1};\n    }\n};\n```
['C', 'C++']