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 the 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 to the right and have a better solution. So we have
d, d, c .... d, c, c, c ^ .... ^ <- solution indexes Now, since d <> c we can improve the solution into
d, d, c .... d, c, c, c ^ .... ^ <- solution indexes ^ .... ^ <- better solution We have a contradiction 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