Find the Maximum difference between two Same Numbers in an unsorted array of integers in best Time Complexity [Java]

Question

static int solution(int[] A) {
    int N = A.length;
    int result = 0;
    Map<Integer, List<Integer>> map = new TreeMap<>();
    for (int i = 0; i < N; i++) {
        List<Integer> list = map.getOrDefault(A[i], new ArrayList<>());
        list.add(i);
        map.put(A[i], list);

    }
    for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
        List<Integer> list = map.get(entry.getKey());
        Collections.sort(list);
        result = Math.max(result, (list.get(list.size() - 1) - list.get(0)));
    }
    return result;
}

With this above solution we can solve the problem but it is not O(N) time complexity. So I am looking for an optimized solution for this problem in Java.

Answer 1

// Collections.sort(list);//Removing this line makes O(NlogK) to O(N) time complexity

  static int solution(int[] A) {
    int N = A.length;
    int result = 0;
    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < N; i++) {
        List<Integer> list = map.getOrDefault(A[i], new ArrayList<>());
        list.add(i);
        map.put(A[i], list);

    }
    for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
        List<Integer> list = map.get(entry.getKey());
        result = Math.max(result, (list.get(list.size() - 1) - list.get(0)));
    }
    return result;
}

Answer 2

One of the solution is loop through all elements and keep track of only first and last occurence as follow:

class Pair<F, S> {
    F first;
    S second;
    constrcutor(F first, S second) {
        this.first = first;
        this.second = second;
    }
}

    static int solution(int arr[]) {

        // Pair.first will contain the first occurrence and Pair.second will contain the last occurrence of number
        HashMap<Integer, Pair<Integer, Integer>> minMaxMap = new HashMap<>();
        for (int index = 0; index < arr.length; index++) {
            Pair<Integer, Integer> existingValue = minMaxMap.get(arr[index]);
            if (existingValue == null) {
                minMaxMap.put(arr[index], new Pair<Integer, Integer>(index, index));
            } else {
                existingValue.second = index; // update the Pair.second to latest value.
            }
        }

        int result = 0;
        for (Pair<Integer, Integer> pair : minMaxMap.values()) {
            int difference = pair.second - pair.first;
            if (difference > result) {
                result = difference;
            }
        }
        return result;
    }

In your solution, since we are using list, it requires more memory in case the array contains a lot of duplicate element. By avoiding list, you can even reduce the memory footprint.

Answer 3

I think this looks like an efficient solution - it doesn't use any collections and doesn't need to loop through all values. It checks for pair at the maximum distance (same numbers at both array ends), then maximum distance-1 and so on, only until the pair is found.

static int solution(int[] A) {
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < i; j++) {
            if (A[j] == A[j + A.length - i])
                return A.length - i;
        }
    }
    return -1; //-1 stands for no equal numbers
}