Last Updated: 20 Sep, 2020
Day 18 : Maximum Distance
Easy
Asked in companies
You have been given an array ‘ARR’ that might contain duplicate elements. Your task is to find the maximum possible distance between occurrences of two repeating elements i.e. elements having the same value. If there are no duplicate elements in the array, return 0.
Input Format:
The first line of input contains an integer N denoting the length of the array.
The second line of input contains N integers denoting the elements of the array 'ARR'.
Output Format:
The output prints a single line containing an integer denoting the maximum distance.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
0 <= N <= 10^6
-10^9 <= ARR[i] <= 10^9
Time Limit: 1sec
Approaches
In the brute force approach, to consider all pairs we will use two nested loops. The outer loop is used to select one element for the pair and the inner loop will select another element. Now if both the elements are equal we will update the maximum distance with the distance between them if the distance between both is greater than the maximum distance.
- In approach 1 if you observe that the maximum distance is the maximum of all the maximum distance for each repeating element.
- The maximum distance for each repeating element equals the distance between its leftmost index and rightmost index.
- We will use a hashmap that will store the element as a key and its value as the leftmost index of the element.
- For each element in the array,
- If the current element exists in the map we will update the maximum distance by the current distance as (current INDEX - leftmost index in the map) if the current distance is greater than the maximum distance.
- Otherwise, we will insert the element and its index into the MAP.