Maximum Distance Between two Occurrences of Same Element in Array

Difficulty Level Medium
Frequently asked in Delhivery Factset Fanatics Fourkites
Array HashViews 4155

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 [1] 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 [0] and array [7] 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.

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.

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[0]);
    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.*;

class distanceBSameNumbers
{
    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.

Translate »