Simple (not nested) loop is enough, but two cases should be taken into account: either the best result is
4,6,2,2,6,6,4 ^ ^ - moving first
or
4,6,2,2,6,6,4 ^ ^ - moving last
for instance: [4, 2, 4, 4, 4] moving first brings the answer, when in case of [4, 4, 4, 2, 4] moving last should be used.
int first = 0; int last = A.length - 1; // 1st case: moving "first" while (first < last) { if (A[first] == A[last]) first++; else break; } int diff1 = last - first; first = 0; last = A.length - 1; // 2nd case: moving "last" while (first < last) { if (A[first] == A[last]) last--; else break; } int diff2 = last - first; // result is the max between two cases int result = diff1 > diff2 ? diff1 : diff2;
So we have O(N) time complexity.
Edit: Let's proof that at least one of the indexes is either 0 or length - 1. Let's do it by contradiction. Suppose we have a solution like
a, b, c, .... d, e, f, g ^ ..... ^ <- solution indexes (no borders)
Items to the left of c must be d, otherwise we can take a or b indexes and have an improved solution. Items to right of d must be c or we can once again push last index to the right and have a better solution. So we have
d, d, c .... d, c, c, c ^ .... ^ <- solution indexes
Now, since d <> c (c..d is a solution) we can improve the solution into
d, d, c .... d, c, c, c ^ .... ^ <- solution indexes ^ .... ^ <- better solution
We have a contradiction (the supposed solution is not one - we have a better choice) and that's why at least one index must be 0 or length - 1.
Now we have 2 scenarions to test:
a, b, ..... y, z ^ ...... ^ <- moving first ^ ...... ^ <- moving last
We can combine both conditions into if and have just one loop:
int result = 0; for (int i = 0; i < A.length; ++i) if (A[i] != A[A.length - 1] || A[0] != A[A.length - 1 - i]) { result = A.length - i - 1; break; }
