## Codility Challenge “Argon 2015” solution

Codility might not be the best way to assess a candidate (especially
if it is the only one!), but there is definitely something in it that I like.
The idea of my solution to a programming task being automatically evaluated after I deem it *ready*
is not unfair—after all, programs are run by machines and have to be correct, efficient
(more or less, depending on the context), and handle corner cases.

But the thing I like most of Codility are, of course, the challenges. I find them both difficult (I envy those who can solve them in 15 minutes at the first attempt) and fun. For me they are more workable than Project Euler’s problems, which are indeed interesting but difficult to understand if you don’t hold a degree in mathematics.

Good solutions for Codility challenges are not easy to find, and when you find one, in most cases it’s a huge blob of code with no explanation. Let’s try to solve Argon 2015 step by step.

You are given an array of`0`

s and`1`

s. You have to find thelength of a longest sliceof it that can be split intotwo non-empty parts: in theleft part, there should bemore; in the`0`

s than`1`

sright part, there should bemore. The algorithm must run in`1`

s than`0`

slinear time and linear additional spacewith respect to the size of the input array.

**Example**. The result for the input
`[ 1 `

is **1 0 1 0 0 1 1** ]** 7**,
the longest slice being highlighted in

**bold**with the left part in

**red**and the right part in

**blue**.

Of course the problem can be solved in place with a handful of nested `for`

loops achieving O(n^{3})
time complexity, but **linear time complexity is a requirement**.

The first observation we can make is that **every sequence starting with a 0 and ending with a 1
does respect the rule** of being “splittable” in two non-empty parts, where the left one has more

`0`

s
than `1`

s, and the right one has more `1`

s than `0`

s.
For `0 1`

this is trivially true, and for
`0 ? ? ? ... ? ? ? 1`

we can say that if among the question marks there are more `0`

s than `1`

s
they all belong to the left part, if there are more `1`

s than `0`

s they all belong to the right part, otherwise they may all
belong to either.A good step towards the solution is to **select the subsequence starting with the first 0 and ending
with the last 1**. But that’s not enough: depending on the actual split point between the left
and the right part, the subsequence we have selected may be able to “grab” more

`1`

s from the left and/or
more `0`

s from the right. If we take our example:
`[ 1 1 0 1 0 0 1 1 ]`

, we see that the subsequence starting from the first `0`

and ending with the
last `1`

is `[ 1 1 `**0 1 0 0 1 1** ]

(highlighted in **bold**), but we can definitely grab another

`1`

from the left if we split the sequence at the right point:
`[ 1 `**1 0 1 0 0 | 1 1** ]

.The idea is to try every possible split point and see which one allows us to grab more `1`

s from the left
and/or `0`

s from the right. In fact, the amount of elements we can grab depends on how many “spare” `0`

s
we have in the left part, and how many “spare” `1`

s we have in the right part. Therefore we can build two auxiliary arrays,
the first one (`#1`

) telling how many spare `0`

s we have in
the left part if it __ends__ at a given position, the second one (`#2`

) telling
how many spare `1`

s we have in the right part if it __begins__ at a given position:

#1: 0 -1 0 1 0 -1 #2: -1 0 -1 0 1 0 [ 1 1 0 1 0 0 1 1 ] split pos: 0 1 2 3 4 5

If we split between positions `3`

and `4`

, we can grab a `0`

from the left and a
`1`

from the right (which does not exist in this case). This is the solution for the example instance.

`#1`

and `#2`

can be built in linear time by using an accumulator, and that’s simple
to understand by just looking at the code.

Here is the full solution (also on GitHub):

#include <vector> #include <algorithm> int solution(std::vector<int>& input) { // find first zero and last one int first_zero = -1, last_one = -1; for (int i = 0; i < input.size(); i++) { if (input[i] == 0 && first_zero == -1) first_zero = i; else if (input[i] == 1) last_one = i; } if (first_zero == -1 || last_one == -1 || first_zero > last_one) // no solution { return 0; } // Compute "head" and "tail" length const int head_length = first_zero; const int tail_length = input.size() - 1 - last_one; // Isolate the region of the vector from the first zero to the last one const std::vector<int> core(input.begin() + first_zero, input.begin() + last_one + 1); // Compute maximum elements that we can grab from the "head" or the "tail" int spare; std::vector<int> spare_left(core.size()), spare_right(core.size()); spare = -1; for (int i = 0; i < core.size(); i++) { spare_left[i] = (core[i] == 0) ? ++spare : --spare; } spare = -1; for (int i = core.size() - 1; i >= 0; i--) { spare_right[i] = (core[i] == 1) ? ++spare : --spare; } int max_grab = 0; for (int split_pos = 0; split_pos < core.size() - 1; split_pos++) { const int grab_left = std::max(0, std::min(head_length, spare_left[split_pos])); const int grab_right = std::max(0, std::min(tail_length, spare_right[split_pos + 1])); max_grab = std::max(max_grab, grab_left + grab_right); } return core.size() + max_grab; }

If there is anything unclear, or you spotted a mistake, or you have an alternative (possibly better)
solution, please **post a comment**.