Maximum Distance Between two Occurrences of Same Element in Array

Difficulty Level Medium
Frequently asked in Delhivery Factset Fanatics Fourkites
Array Hash

Suppose you are given an array with some repeated numbers. We have to find the maximum distance between the two same occurrences of a number with different index, present in an array.

Example

Input:

array = [1, 2, 3, 6, 2, 7]

Output:

3

Explanation:

Because elements at array  and array [ 4 ] have the same elements that are ‘2’ with a maximum distance of 3.

Input:

array=[3, 4, 6, 7, 4, 8, 9, 3]

Output:

7

Explanation:

Because element array  and array  have the same elements that are ‘3’ with a maximum distance of 3.

Algorithm for Maximum Distance Between two Occurrences of Same Element

1. Declare a map.
2. Set “maxDistance” to 0.
3. While i is less than the length of the array (n).
1. Check each array element if it has its first occurrence or not in a map, if first,
1. Then put the element and its index in a map.
2. Else (if it already exists)
1. Find out the maximum distance between the previous one and this one (distance between index).
2. Store maximum distance to “maxDistance”.
4. Return “maxDistance”.

Explanation

We have given an array with some repeated elements in it. Our task is to find out the maximum difference between the position of the same occurrences of a number. We are going to use a map for this. In that map, we are going to put array elements as a key and their index as value. Then we are going to find the maximum difference or distance between the two indexes of the same number if it exists, although we need to find the distance between the same elements.

Queries on XOR of greatest odd divisor of the range

In a map, each key has some value in it as array’s element and their indexes, if for each element there are two indexes found, then we are going to find the difference between those indexes and find the bigger difference between the previous “maxDistance” and the present one. And then after iterating over the whole array we have the biggest maximum distance.

Let us consider an example:

Example

arr[] = {8, 1, 3, 2, 4, 1, 3, 6, 7, 3, 1};

i=0, arr[i]=8  => myMap={8:0}

i=1, arr[i]=1  => myMap={ 8:0, 1:1}

i=2, arr[i]=3  => myMap={ 8:0,  1:1, 3:2}

i=3, arr[i]=2  => myMap={ 8:0,  1:1, 3:2, 2:3}

i=4, arr[i]=4  => myMap={ 8:0,  1:1, 3:2, 2:3, 4:4}

i=5, arr[i]=1  => myMap={ 8:0,  1:1, 3:2, 2:3, 4:4}, Here it will find the difference between the present index and previous index of  ‘1’,  (5-1=4), 4 is store in maxDistance.

i=6, arr[i]=3  => myMap={ 8:0,  1:1, 3:2, 2:3, 4:4} Here it will find the difference between the present index and previous index of  ‘3’,  (6-2=4),but 4 is already in maxDistance, so it doesn’t matter.

i=7, arr[i]=6  => myMap={ 8:0,  1:1, 3:2, 2:3, 4:4, 6:7}

i=8, arr[i]=7  => myMap={ 8:0,  1:1, 3:2, 2:3, 4:4, 6:7, 7:8}

i=9, arr[i]=3  => myMap={ 8:0,  1:1, 3:2, 2:3, 4:4, 6:7, 7:8} Here it will find the difference between the present index and previous index of  ‘3’,  (9-3=6), 6 is store in maxDistance.

i=10, arr[i]=3  => myMap={ 8:0,  1:1, 3:2, 2:3, 4:4, 6:7, 7:8} Here it will find the difference between the present index and previous index of  ‘1’,  (10-1=9), 9 is store in maxDistance.

Matrix Diagonal Sum Leetcode Solution

And we return maxDistance as 9.

Implementation

C++ program for Maximum Distance Between two Occurrences of Same Element in array

#include<bits/stdc++.h>
using namespace std;

int getDistance(int arr[], int n)
{
unordered_map<int, int> my_map;
int maxDistance = 0;
for (int i=0; i<n; i++)
{
if (my_map.find(arr[i]) == my_map.end())
my_map[arr[i]] = i;
else
maxDistance = max(maxDistance, i - my_map[arr[i]]);
}

return maxDistance;
}
int main()
{
int arr[] = {8, 1, 3, 2, 4, 1, 3, 6, 7, 3, 1};
int n = sizeof(arr)/sizeof(arr);
cout << getDistance(arr, n);
return 0;
}
9

Java program for Maximum Distance Between two Occurrences of Same Element in array

import java.io.*;
import java.util.*;

{
static int getDistance(int[] arr, int n)
{
HashMap<Integer,Integer> my_map = new HashMap<>();

int maxDistance = 0;

for (int i = 0; i < n; i++)
{
if (!my_map.containsKey(arr[i]))
my_map.put(arr[i], i);

else
maxDistance = Math.max(maxDistance, i - my_map.get(arr[i]));
}

return maxDistance;
}
public static void main(String args[])
{
int arr[] = {8,1,3,2,4,1,3,6,7,3,1};
int n = arr.length;
System.out.println(getDistance(arr, n));
}
}
9

Complexity Analysis for Maximum Distance Between two Occurrences of Same Element in array

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.