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.

CodePudding user response：

// 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;
}

CodePudding user response：

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

    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.