// max distance between two occurance of same elem optimised using hashmap
import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone {
    public static int maxDistance(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        int maxDist = 0;
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                int dist = i - map.get(arr[i]);
                maxDist = Math.max(maxDist, dist);
            } else {
                map.put(arr[i], i); 
            }
        }
 
        return maxDist;
    }
 
    public static void main(String[] args) throws java.lang.Exception {
        int[] arr = {1, 1, 2, 2, 2, 1};
        System.out.println("Max Distance: " + maxDistance(arr)); 
 
    }
}
 

Ly8gbWF4IGRpc3RhbmNlIGJldHdlZW4gdHdvIG9jY3VyYW5jZSBvZiBzYW1lIGVsZW0gb3B0aW1pc2VkIHVzaW5nIGhhc2htYXAKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBJZGVvbmUgewogICAgcHVibGljIHN0YXRpYyBpbnQgbWF4RGlzdGFuY2UoaW50W10gYXJyKSB7CiAgICAgICAgTWFwPEludGVnZXIsIEludGVnZXI+IG1hcCA9IG5ldyBIYXNoTWFwPD4oKTsKICAgICAgICBpbnQgbWF4RGlzdCA9IDA7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhcnIubGVuZ3RoOyBpKyspIHsKICAgICAgICAgICAgaWYgKG1hcC5jb250YWluc0tleShhcnJbaV0pKSB7CiAgICAgICAgICAgICAgICBpbnQgZGlzdCA9IGkgLSBtYXAuZ2V0KGFycltpXSk7CiAgICAgICAgICAgICAgICBtYXhEaXN0ID0gTWF0aC5tYXgobWF4RGlzdCwgZGlzdCk7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBtYXAucHV0KGFycltpXSwgaSk7IAogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gbWF4RGlzdDsKICAgIH0KCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbiB7CiAgICAgICAgaW50W10gYXJyID0gezEsIDEsIDIsIDIsIDIsIDF9OwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiTWF4IERpc3RhbmNlOiAiICsgbWF4RGlzdGFuY2UoYXJyKSk7IAogICAgICAgIAogICAgfQp9Cg==