700402. Max distance between same elements
Max distance between same elements
Slug: max-distance-between-same-elements Difficulty: Easy Id: 700402 Topic Tags: Arrays, Hash, Data Structures Company Tags: None
Summary
Given an array of integers, find the maximum distance between two occurrences of the same element. The distance is calculated as the absolute difference between their indices.
For example, if the input array is [1, 2, 3, 4, 5, 6, 7], the output should be 4 because the distance between the first occurrence of 1 at index 0 and the second occurrence at index 4 is 4.
Detailed Explanation
To solve this problem, we can use a hash map to store the indices of each element. Then, for each element, we calculate its distance from the previous occurrence.
Here's a step-by-step breakdown:
- Initialize an empty hash map.
- Iterate through the array and for each element:
- Check if the element is already in the hash map.
- If it's not, add it to the hash map with its current index as the value.
- If it is, calculate the distance between the current index and the previous index stored in the hash map.
- Keep track of the maximum distance found so far.
Time complexity: O(n), where n is the length of the array. Space complexity: O(min(n, m)), where m is the number of unique elements in the array.
Optimized Solutions
Java
import java.util.HashMap;
import java.util.Map;
public class MaxDistance {
public static int maxDistance(int[] arr) {
Map<Integer, Integer> indices = new HashMap<>();
int maxDist = 0;
for (int i = 0; i < arr.length; i++) {
if (!indices.containsKey(arr[i])) {
indices.put(arr[i], i);
} else {
int dist = i - indices.get(arr[i]);
maxDist = Math.max(maxDist, dist);
indices.put(arr[i], i);
}
}
return maxDist;
}