Maximum distance between two occurrences of same element in array

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.

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

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

Run Code

Output 

8

Code in python

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

Run Code

Output 

8

Code in Java

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

Run Code

Output 

8

Time complexity: O(n) 

We had used  unordered_map’s search and insert operations take O(1) time.

Auxiliary Space: O(n)

We used unordered_map to store the elements and their indexes.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Question

What is an array?

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

• Count divisible pairs in an array
• Find three-element from different three arrays such that a + b + c = sum
• Check if an array can be divided into pairs whose sum is divisible by k
   

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k
• Find Duplicate In Array

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. 

Enroll in our courses and refer to the mock test and problems available.

Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Happy Coding!