Max Distance between two occurrences of the same element

Given an array of integers where elements may be repeating in the array. Find the maximum distance between two occurrences of the same element in the array.

For example:

Input array: 
int[] a = {5, 4, 8, 1, 2, 6, 4, 5, 2, 8, 9, 1, 6, 4};
Output: 12

(The distance between first and last occurrences of 4 in the array).

Solution – 1 (Brute Force):

The brute-force solution for this problem is to pick each element in the array and then find the first and last occurrence of that element in the array.

public static int getMaxDistance(int[] arr) 
{
   int maxDist = 0;
   for(int i=0; i<arr.length; i++)
   {
      int firstOcc = -1;
      int lastOcc = -1;
      
      for(int j=0; j<arr.length; j++)
      {
         if(arr[i] == arr[j])
         {
            if(firstOcc == -1)
               firstOcc = lastOcc = j;
            else
               lastOcc = j;
         }
      }
      if(lastOcc - firstOcc > maxDist)
         maxDist = lastOcc - firstOcc;
   }
   return maxDist;
}

This solution takes O(n^2) time. The next solution uses an extra memory for Hash but solves the problem in linear time.

Solution -2 (Using Hash)

Use a hashmap. Traverse the given array and store index of the first occurrence in the hash.

For every other occurrence, find the difference of that index from the first index stored in the hash. Keep a track of the maximum distance found till now.

Code:

public class RitambharaUtils 
{
   public static int getMaxDistance(int[] arr) 
   { 
      if(arr.length == 0){ return -1; } // WHEN ARRAY HAS 0 ELEMENTS
      
      HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); 
        
      int maxDistance = 0; 
  
      for (int i = 0; i < arr.length; i++) 
      { 
         if (!hash.containsKey(arr[i]))
         {
            hash.put(arr[i], i);
         }
         else
         {
            int dist = i - hash.get(arr[i]);
            if(dist > maxDistance)
               maxDistance = dist;
         }
      } 
      return maxDistance; 
   } 
   
   public static void main(String[] args)
   {
      int[] a = {5, 4, 8, 1, 2, 6, 4, 5, 2, 8, 9, 1, 6, 4};
      System.out.println(getMaxDistance(a));
   }
}