Maximum distance between two different element in an array

Question

I have a problem where I need to find the maximum distance between two different elements in an array.

For example: given an array 4,6,2,2,6,6,4 , the method should return 5 as the max distance.

I am able to solve the problem using two for loops but it is not an optimized solution. Am trying to optimize it by doing it in a single for loop.

here is my current solution:

int [] A = {4,6,2,2,6,6,4};
int N = A.length;
int result = 0;

for (int i = 0; i < N; i++){
    for (int j = i; j < N; j++) {
        if(A[i] != A[j]){
            result = Math.max(result, j - i);
        }
    }
}

// tried below code but it is not efficient
//      for (int i = 0; i < N; i++){
//          
//          if(A[N-1] != A[i]){
//              result = Math.max(result, N-1-i);
//          }
//      }

System.out.println(result);

How to make this better in terms of time complexity?

Answer 1

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;
    }