Max distance between same elements

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

For each value, find maximum distance between first and last occurrence.

Algorithm

1HashMap: store first occurrence index. For each element: if seen, update max distance = i - firstIndex[val].

Common Pitfalls

•Only store first occurrence. At each re-occurrence update answer. O(n) single pass.

Max distance between same elements.java

Java

// Approach: HashMap storing first index of each element. For each recurrence, update max distance.
// Time: O(n) Space: O(n)
class Solution {
    public int maxDistance(int[] arr) {
        int res = 0;
        HashMap<Integer, Integer> mp = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            if (!mp.containsKey(arr[i]))
                mp.put(arr[i], i);
            else
                res = Math.max(res, i - mp.get(arr[i]));
        }
        return res;
    }
}

Was this solution helpful?