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?

**Solution:**

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

### Like this:

Like Loading...