In this article, weâ€™ll be looking at one problem namedMaximum distance between two occurrences of same element in array.

We are going to solve this problem with the help of a set data structure that is going to be used in storing the element and its frequency. we will also discuss the step-wise algorithm along with the time and space complexity.

Given an array with repeated elements, the task is to find the maximum distance between two occurrences of an element.

Arr[] = { 8,2,4,8,3,4,6,5,2,5 }

Output = 7

The maximum distance between two occurrences of element 2 is 7.

Explanation

Element occurred twice is 8, 2, 4, 5

The maximum distance between 8 is 3 - 0 = 3

The maximum distance between 2 is 8 - 1 = 7

The maximum distance between 4 is 5 - 2 = 3

The maximum distance between 5 is 9 - 7 = 2

Hence the max distance is 7, so the output will be 7

Approach

In this Maximum distance between two occurrences of same element in array problem a simple and brute force approach will be to run two loops and find the first and last occurrence of an element one by one. This approach will take O(n^2) time.

The Efficient approach will be using a hash table. The goal is to iterate through the input array and record the first instance's index in a hash map. Calculate the difference between the index and the initial index kept in the hash map for each further occurrence. Update the result if the difference exceeds the previous finding. This will solve the problem in O(n) time.

Algorithm

Create a function that takes an array as input.

Create an ordered map to store the index of the first occurrence of an element.

Initialize a variable that stores the max distance between an element's first and last occurrence.

Insert the element in the map if it is the first occurrence of the element.

If it is the second occurrence of the element, update the max distance variable.

Return the max distance variable.

Let's understand the algorithm with the help of an example.

Arr[] = { 2, 3, 5, 2, 6, 5, 8, 9, 4, 3 }

Step 1: Lets the max distance variable dis = 0 at starting.

Step 2: Create a hash table to store the occurrence of elements.

Element

Index

variable

2

0

dis = 0

3

1

dis = 0

5

2

dis = 0

Step 3: When multiple occurrences of the element appear, update the distance variable by [index of current occurrence - index of first occurrence]

2

0

dis = 0

3

1

dis= 0

5

2

dis = 0

dis = 3 - 0 = 3

6

4

dis = 3

dis = 5 - 2 = 3

8

6

dis = 3

9

7

dis = 3

4

8

dis = 3

dis = 9 - 1 = 8

Step 4: Return the dis variable ie = 8.

Code in C++

Implementation of C++ code to Maximum distance between two occurrences of same element in array.

#include <bits/stdc++.h>
using namespace std;
int maxi_dis(vector<int> &arr)
{
unordered_map<int, int> mp;
int n = arr.size();
int dis = INT_MIN;
for (int i = 0; i < n; i++)
{
if (mp.find(arr[i]) != mp.end())
dis = max(dis, i - mp[arr[i]]);
else
mp[arr[i]] = i;
}
return dis;
}
int main()
{
vector<int> arr = {2, 3, 5, 2, 6, 5, 8, 9, 4, 3};
cout << maxi_dis(arr);
return 0;
}

You can also try this code with Online C++ Compiler

Implementation of Python code to Maximum distance between two occurrences of same element in array.

def maxi_dis(arr, n):
# Used to store element to first index mapping
mp = {}
dis = 0
for i in range(n):
#check for occurrence of element
if arr[i] not in mp.keys():
mp[arr[i]] = i
else:
dis = max(dis, i-mp[arr[i]])
return dis
if __name__=='__main__':
arr = [2, 3, 5, 2, 6, 5, 8, 9, 4, 3]
n = len(arr)
print (maxi_dis(arr, n))

You can also try this code with Online Python Compiler

Implementation of Java code to Maximum distance between two occurrences of same element in array.

import java.util.*;
public class Main
{
public static int maxi_dis(ArrayList<Integer> arr)
{
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
int n = arr.size();
int dis = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
{
if (mp.containsKey(arr.get(i)))
{
dis = Math.max(dis, i - mp.get(arr.get(i)));
}
else
{
mp.put(arr.get(i), i);
}
}
return dis;
}
public static void main(String[] args)
{
ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList(2, 3, 5, 2, 6, 5, 8, 9, 4, 3));
System.out.print(maxi_dis(arr));
}
}

You can also try this code with Online Java Compiler

An array is a collection of homogeneous values stored at contiguous memory locations. It is like a staircase, in which each value of placed at every step, and elements can be accessed by knowing the stair number (or index number).

What is Hashing?

Hashing is a technique using which a given value can be transformed into another value. It makes searching more accessible and quicker.

What is an unordered_set?

An unordered set is a data structure that is an associative container that holds a collection of singular Key objects. Average constant-time complexity characterizes search, insertion, and removal. Internally, the components are arranged into buckets rather than being sorted in any specific sequence.

WhÐ°t Ð°re the three bÐ°sic operÐ°tions on Ð° hÐ°sh tÐ°ble?

There are mainly three basic operations of a hash table.

Insert âˆ’ inserts Ð°n element in Ð° hÐ°sh tÐ°ble.

SeÐ°rch âˆ’ SeÐ°rches Ð°n element in Ð° hÐ°sh tÐ°ble.

Delete âˆ’ Deletes Ð°n element from Ð° hÐ°sh tÐ°ble.

What does unordered_set mean?

An unordered set is an associative container with a collection of singular Key objects. The complexity of search, insertion, and removal is often constant-time. Internally, the components are arranged into buckets rather than sorted in any specific sequence.

Conclusion

In this article, we have extensively discussed the problem of Maximum distance between two occurrences of same element in array

We hope that this blog has helped you enhance your knowledge of the array data structure and set traversal and if you would like to learn more, check out our articles on