Maximum distance between two occurrences of same element in array
Last Updated :
11 Sep, 2023
Given an array with repeated elements, the task is to find the maximum distance between two occurrences of an element.
Examples:
Input : arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Output: 10
// maximum distance for 2 is 11-1 = 10
// maximum distance for 1 is 4-2 = 2
// maximum distance for 4 is 10-5 = 5
A simple solution for this problem is to, one by one, pick each element from the array and find its first and last occurrence in the array and take the difference between the first and last occurrence for maximum distance.
Below is the implementations of the idea.
C++
#include <bits/stdc++.h>
int maxDistance(int arr[], int n)
{
int maxD = -1;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] == arr[j]) {
int temp = abs(j - i);
maxD = maxD > temp ? maxD : temp;
}
return maxD;
}
int main()
{
int Arr[] = { 1, 2, 4, 1, 3, 4, 2, 5, 6, 5 };
printf("Maximum distance between two occurrences of "
"same element in array:%d",
maxDistance(Arr, 10));
return 0;
}
|
Java
import java.util.*;
public class Main {
public static int maxDistance(int[] arr, int n)
{
int maxD = -1;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) {
int temp = Math.abs(j - i);
maxD = maxD > temp ? maxD : temp;
}
}
}
return maxD;
}
public static void main(String[] args)
{
int[] Arr = { 1, 2, 4, 1, 3, 4, 2, 5, 6, 5 };
System.out.printf(
"Maximum distance between two occurrences of same element in array:%d",
maxDistance(Arr, 10));
}
}
|
Python3
def max_distance(arr):
n = len(arr)
max_d = -1
for i in range(n - 1):
for j in range(i + 1, n):
if arr[i] == arr[j]:
temp = abs(j - i)
max_d = max(max_d, temp)
return max_d
arr = [1, 2, 4, 1, 3, 4, 2, 5, 6, 5]
print("Maximum distance between two occurrences of same element in array:", max_distance(arr))
|
C#
using System;
class MainClass {
public static int maxDistance(int[] arr, int n)
{
int maxD = -1;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) {
int temp = Math.Abs(j - i);
maxD = maxD > temp ? maxD : temp;
}
}
}
return maxD;
}
public static void Main(string[] args)
{
int[] Arr = { 1, 2, 4, 1, 3, 4, 2, 5, 6, 5 };
Console.WriteLine(
"Maximum distance between two occurrences of same element in array: {0}",
maxDistance(Arr, 10));
}
}
|
Javascript
function maxDistance(arr) {
let dict = {};
let maxD = -1;
for (let i = 0; i < arr.length; i++) {
if (dict[arr[i]] !== undefined) {
let temp = i - dict[arr[i]];
maxD = maxD > temp ? maxD : temp;
} else {
dict[arr[i]] = i;
}
}
return maxD;
}
let Arr = [1, 2, 4, 1, 3, 4, 2, 5, 6, 5];
console.log("Maximum distance between two occurrences of same element in array: " + maxDistance(Arr));
|
Output
Maximum distance between two occurrences of same element in array:5
Time complexity : O(n2)
Auxiliary Space : O(1)
An efficient solution to this problem is to use hashing. The idea is to traverse the input array and store the index of the first occurrence in a hash map. For every other occurrence, find the difference between the index and the first index stored in the hash map. If the difference is more than the result so far, then update the result.
Below are implementations of the idea. The implementation uses unordered_map in.
C++
#include<bits/stdc++.h>
using namespace std;
int maxDistance(int arr[], int n)
{
unordered_map<int, int> mp;
int max_dist = 0;
for (int i=0; i<n; i++)
{
if (mp.find(arr[i]) == mp.end())
mp[arr[i]] = i;
else
max_dist = max(max_dist, i - mp[arr[i]]);
}
return max_dist;
}
int main()
{
int arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << maxDistance(arr, n);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG
{
static int maxDistance(int[] arr, int n)
{
HashMap<Integer, Integer> map = new HashMap<>();
int max_dist = 0;
for (int i = 0; i < n; i++)
{
if (!map.containsKey(arr[i]))
map.put(arr[i], i);
else
max_dist = Math.max(max_dist, i - map.get(arr[i]));
}
return max_dist;
}
public static void main(String args[])
{
int[] arr = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2};
int n = arr.length;
System.out.println(maxDistance(arr, n));
}
}
|
Python3
def maxDistance(arr, n):
mp = {}
maxDict = 0
for i in range(n):
if arr[i] not in mp.keys():
mp[arr[i]] = i
else:
maxDict = max(maxDict, i-mp[arr[i]])
return maxDict
if __name__=='__main__':
arr = [3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2]
n = len(arr)
print (maxDistance(arr, n))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static int maxDistance(int[] arr, int n)
{
Dictionary<int, int> map = new Dictionary<int, int>();
int max_dist = 0;
for (int i = 0; i < n; i++)
{
if (!map.ContainsKey(arr[i]))
map.Add(arr[i], i);
else
max_dist = Math.Max(max_dist, i - map[arr[i]]);
}
return max_dist;
}
public static void Main(String []args)
{
int[] arr = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2};
int n = arr.Length;
Console.WriteLine(maxDistance(arr, n));
}
}
|
Javascript
<script>
function maxDistance(arr, n)
{
let map = new Map();
let max_dist = 0;
for (let i = 0; i < n; i++)
{
if (!map.has(arr[i]))
map.set(arr[i], i);
else
max_dist = Math.max(max_dist, i - map.get(arr[i]));
}
return max_dist;
}
let arr = [3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2];
let n = arr.length;
document.write(maxDistance(arr, n));
</script>
|
Time complexity : O(n) under the assumption that unordered_map’s search and insert operations take O(1) time.
Auxiliary Space : O(n).
Shashank Mishra ( Gullu )
Please Login to comment...