Max distance between same elements

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

Example 1:

Input
n= 6
arr = {1, 1, 2, 2, 2, 1}

Output
5

Explanation
arr[] = {1, 1, 2, 2, 2, 1}
Max Distance: 5
Distance for 1 is: 5-0 = 5
Distance for 2 is : 4-2 = 2
Max Distance 5

Example 2:

Input
n = 12
arr = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}

Output
10

Explanation



arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Max Distance 10
maximum distance for 2 is 11-1 = 10
maximum distance for 1 is 4-2 = 2
maximum distance for 4 is 10-5 = 5

method 1 :

The idea is to traverse input array and store index of only first occurrence in a hash map. For every other occurrence, find the difference between index and the first index and store it in variable. If difference is more than result so far, then update the result.

c++ implementation:

int maxDistance(int a[], int n)
    {
        map<int,int>m;
        
        int k=0;
        int x=0;
       for(int i=0;i<n;i++)
       {
          if(m.find(a[i])!=m.end())
          {
            k=i-m[a[i]];
            x=max(x,k);
          }
          else
          m[a[i]]=i;
          
       }
       return x;
    }

Time Complexity: O(n) 

space Complexity: O(n)