CODEWITHSUNDEEP
javaarraysalgorithminteger
roger_that
roger_that

Reputation: 9791

Maximum distance between two different element in an array

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?

Upvotes: 6

Views: 9482

Answers (2)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186688

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

Upvotes: 8

thebenman
thebenman

Reputation: 1621

This can be done in a single loop

Consider this.

The maximum difference between from a index i can be either between start element and i or i and the last element

int main() {
    vector<int> v {4, 6, 2, 2, 6, 6, 4};
    int start = 0, end = v.size() -1;
    int result = 0;
    for(int i=0; i< v.size(); ++i)
    {
        if(v[i] != v[start])
        {
            result = max(result, i);
        }
        if(v[i] != v[end])
        {
            result = max(result, end - i);
        }
    }
    return result;
}

The reason we are able to achieve a O(N) algorithm is because

Consider v = [4, 4, 2, 3, 4, 4]

At index i = 0 we check if we can find the maximum possible distance i.e with the last element but since they are same we can't consider it.

At i = 0 for this array the maximum possible answer would have been 5. 

[4, 4, 2, 3, 4, 4]
 ^

At i = 1 we again check both ends of the array still the same so we move on.

The real savings come here that we do not have to check for every other entry keeping the start at i = 0

So, at i = 2, we find that the maximum can be obtained with the end of the array

[4, 4, 2, 3, 4, 4]
 ^     ^        ^
start  i       end

which is the same as keeping the start constant and keeping a runner loop.

Upvotes: 3

Related Questions