Max distance between same elements

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

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

See our study guide for structured GFG and LeetCode practice.

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?