[Solved] Array coding challenge that needs to be solved in O(n) complexity

Question

Let’s consider your example…

 A = (5, 5, 1, 2, 3, 4, 5)

If you consider the first element – 5 – then we know any solution must have one non-5 value at the other end, so we work backwards to find the first non-five, keeping track of the “front” and “back” locations we’re working at…

 A = (5, 5, 1, 2, 3, 4, 5)
      ^              ^

So, we’ve balanced the 5s so far with the non-5s as we work in from the ends. Now we look at the next position on the left, which is also a five, so we move the right-hand position left until we find another non-five:

 A = (5, 5, 1, 2, 3, 4, 5)
         ^        ^

Now we advance the left-side position looking for another five, but hit the right position before finding one, so the “right-side” position is a solution.

Accepted Answer

Let’s consider your example…

 A = (5, 5, 1, 2, 3, 4, 5)

If you consider the first element – 5 – then we know any solution must have one non-5 value at the other end, so we work backwards to find the first non-five, keeping track of the “front” and “back” locations we’re working at…

 A = (5, 5, 1, 2, 3, 4, 5)
      ^              ^

So, we’ve balanced the 5s so far with the non-5s as we work in from the ends. Now we look at the next position on the left, which is also a five, so we move the right-hand position left until we find another non-five:

 A = (5, 5, 1, 2, 3, 4, 5)
         ^        ^

Now we advance the left-side position looking for another five, but hit the right position before finding one, so the “right-side” position is a solution.