P3A Maximum distance between two occurrences of the same element in an array.

Given an array with repeated elements, the task is to find the maximum distance between two occurrences of an element.

Solution:

A simple solution for this problem is to , one by one, pick each element from the Array and find it’s first and last occurrence for maximum distance.

Below is the implementation of this problem:

 

#include <bits/stdc++.h>

int maxDistance(int arr[], int n)
{


    int maxD = -1;
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)



            if (arr[i] == arr[j]) {
                int temp = abs(j - i);
                maxD = maxD > temp ? maxD : temp;
            }
    return maxD;
}
int main()
{
    int Arr[] = { 1, 2, 4, 1, 3, 4, 2, 5, 6, 5 };
    printf("Maximum distance between two occurrences of "
        "same element in array:%d",
        maxDistance(Arr, 10));
    return 0;
}

The time complexity: O(n^2)

An efficient solution to this problem is to use Hashing.

 #include <bits/stdc++.h>
 
int maxDistance(int arr[], int n)
 
{
 
 int maxD = -1;
 
 for (int i = 0; i < n - 1; i++)
 
 for (int j = i + 1; j < n; j++)
 

 

 
 if (arr[i] == arr[j]) {
 

 
 int temp = abs(j - i);
 
 maxD = maxD > temp ? maxD : temp;
 
 }
 
 return maxD;
 
}
 

 
int main()
 
{
 
 int Arr[] = { 1, 2, 4, 1, 3, 4, 2, 5, 6, 5 };
 
 printf("Maximum distance between two occurrences of "
 
 "same element in array:%d",
 
 maxDistance(Arr, 10));
 
 return 0;
 
}
 
 

#DSA