Given an array with repeated elements, the task is to find the maximum distance between two occurrences of an element.
Example 1:
Input
n= 6
arr = {1, 1, 2, 2, 2, 1}
Output
5
Explanation
arr[] = {1, 1, 2, 2, 2, 1}
Max Distance: 5
Distance for 1 is: 5-0 = 5
Distance for 2 is : 4-2 = 2
Max Distance 5
Example 2:
Input
n = 12
arr = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Output
10
Explanation
arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Max Distance 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
Your Task:
Complete maxDistance() function which takes both the given array and their size as function arguments and returns the maximum distance between 2 same elements. 
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1<=N<=10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: class Solution:

    # Your task is to Complete this function

    # functtion should return an integer

    def maxDistance(self, arr, n):

        # Code here



Solutions:
class Solution:

	def maxDistance(self, arr, n):
		mp = {}
		maxdist = 0
		for i in range(n):
			if arr[i] not in mp.keys():
				mp[arr[i]] = i
			else:
				maxdist = max(maxdist, i - mp[arr[i]])
		return maxdist


class Solution:

	def maxDistance(self, arr, n):
		hashM = {}
		maxx = 0
		for idx in range(n):
			if arr[idx] in hashM:
				maxx = max(maxx, idx - hashM[arr[idx]])
			if arr[idx] not in hashM:
				hashM[arr[idx]] = idx
		return maxx


class Solution:

	def maxDistance(self, arr, n):
		d = {}
		maxdis = 0
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = i
			else:
				currdis = i - d[arr[i]]
				maxdis = max(maxdis, currdis)
		return maxdis


class Solution:

	def maxDistance(self, arr, n):
		dict_ = {}
		ans = {}
		for i in range(n):
			if arr[i] in dict_:
				ans[arr[i]] = i - dict_[arr[i]]
			else:
				dict_[arr[i]] = i
		return max(ans.values()) if ans else 0


class Solution:

	def maxDistance(self, arr, n):
		dist = 0
		dict = {}
		for i in range(n):
			if arr[i] not in dict:
				dict[arr[i]] = i
			elif i - dict[arr[i]] > dist:
				dist = i - dict[arr[i]]
		return dist


from collections import Counter

class Solution:

	def maxDistance(self, arr, n):
		max_distance = 0
		hashmap = {}
		for (i, each) in enumerate(arr):
			if each not in hashmap:
				hashmap[each] = i
			else:
				max_distance = max(max_distance, i - hashmap[each])
		return max_distance


class Solution:

	def maxDistance(self, arr, n):
		d = dict()
		mx = 0
		for i in range(n):
			if arr[i] in d:
				mx = max(mx, i - d[arr[i]])
			else:
				d[arr[i]] = i
		return mx


class Solution:

	def maxDistance(self, arr, n):
		dic_val = dict()
		maxx = 0
		for i in range(len(arr)):
			if arr[i] in dic_val:
				maxx = max(maxx, i - dic_val[arr[i]])
			else:
				dic_val[arr[i]] = i
		return maxx


class Solution:

	def maxDistance(self, arr, n):
		Hash = dict()
		max_dist = 0
		for i in range(n):
			if arr[i] not in Hash:
				Hash[arr[i]] = i
			else:
				max_dist = max(max_dist, i - Hash[arr[i]])
		return max_dist


class Solution:

	def maxDistance(self, arr, n):
		maxi = 0
		hashmap = {}
		for i in range(n):
			if arr[i] not in hashmap:
				hashmap[arr[i]] = i
			else:
				maxi = max(maxi, i - hashmap[arr[i]])
		return maxi


class Solution:

	def maxDistance(self, arr, n):
		mp = dict()
		res = 0
		for i in range(n):
			if arr[i] not in mp:
				mp[arr[i]] = i
			else:
				res = max(res, i - mp[arr[i]])
		return res


class Solution:

	def maxDistance(self, arr, n):
		maxidist = 0
		hashmap = {}
		for i in range(len(arr)):
			if arr[i] in hashmap:
				maxidist = max(maxidist, i - hashmap[arr[i]])
			else:
				hashmap[arr[i]] = i
		return maxidist


class Solution:

	def maxDistance(self, arr, n):
		max_dist = 0
		ele_ind_map = {}
		for i in range(len(arr)):
			if arr[i] in ele_ind_map:
				max_dist = max(max_dist, i - ele_ind_map[arr[i]])
			else:
				ele_ind_map[arr[i]] = i
		return max_dist


class Solution:

	def maxDistance(self, arr, n):
		freq = {}
		for (i, k) in enumerate(arr):
			if k in freq:
				freq[k].append(i)
			else:
				freq[k] = [i]
		max_value = 0
		for i in freq:
			if len(freq[i]) != 1:
				max_value = max(max_value, max(freq[i]) - min(freq[i]))
		return max_value


class Solution:

	def maxDistance(self, arr, n):
		firstTime = {}
		ans = 0
		for (i, n) in enumerate(arr):
			if n in firstTime:
				ans = max(ans, i - firstTime[n])
			else:
				firstTime[n] = i
		return ans


class Solution:

	def maxDistance(self, arr, n):
		dic = {}
		ans = 0
		for i in range(len(arr)):
			if arr[i] in dic.keys():
				ans = max(ans, i - dic[arr[i]])
			else:
				dic[arr[i]] = i
		return ans


class Solution:

	def maxDistance(self, arr, n):
		has = {}
		for i in range(n):
			has[arr[i]] = has.get(arr[i], [])
			has[arr[i]].append(i)
		maxi = 0
		for i in has:
			if len(has[i]) >= 2:
				maxi = max(maxi, abs(has[i][0] - has[i][-1]))
		return maxi


class Solution:

	def maxDistance(self, arr, n):
		max_distance = 0
		first_occurence_dict = {}
		for index in range(len(arr)):
			element_at_index = arr[index]
			if element_at_index in first_occurence_dict:
				distance = index - first_occurence_dict.get(element_at_index)
				if distance > max_distance:
					max_distance = distance
			else:
				first_occurence_dict[element_at_index] = index
		return max_distance


class Solution:

	def maxDistance(self, arr, n):
		seen = {}
		diff = 0
		for i in range(len(arr)):
			if arr[i] in seen:
				diff = max(diff, i - seen[arr[i]])
			else:
				seen[arr[i]] = i
		return diff


class Solution:

	def maxDistance(self, arr, n):
		dic = {}
		lis = [0]
		for i in range(n):
			if arr[i] not in dic:
				dic[arr[i]] = i
			else:
				lis.append(abs(dic[arr[i]] - i))
		return max(lis)


class Solution:

	def maxDistance(self, arr, n):
		from collections import defaultdict
		d = defaultdict(lambda : list())
		for (i, v) in enumerate(arr):
			d[v].append(i)
		ans = 0
		for key in d.keys():
			ans = max(ans, max(d[key]) - min(d[key]))
		return ans


class Solution:

	def maxDistance(self, arr, n):
		dict_ = {}
		max_till = 0
		for index in range(n):
			elem = arr[index]
			c = dict_.get(elem, [])
			c.append(index)
			max_till = max_till if c[-1] - c[0] <= max_till else c[-1] - c[0]
			dict_.update({elem: c})
		return max_till


class Solution:

	def maxDistance(self, arr, n):
		table = {}
		maxi = 0
		for i in range(n):
			if arr[i] in table:
				if i - table[arr[i]] > maxi:
					maxi = i - table[arr[i]]
			else:
				table[arr[i]] = i
		return maxi


class Solution:

	def maxDistance(self, arr, n):
		from collections import OrderedDict
		l1 = []
		l2 = []
		mp = OrderedDict()
		for i in range(n):
			if arr[i] in mp.keys():
				mp[arr[i]] = i
			else:
				mp[arr[i]] = i
				l1.append(i)
		for v in mp.values():
			l2.append(v)
		res = 0
		for j in range(len(l1)):
			res = max(res, l2[j] - l1[j])
		return res


class Solution:

	def maxDistance(self, arr, n):
		distanceMap = dict()
		maxDist = 0
		for (i, num) in enumerate(arr):
			if num in distanceMap:
				maxDist = max(maxDist, i - distanceMap[num])
			else:
				distanceMap[num] = i
		return maxDist


class Solution:

	def maxDistance(self, arr, n):
		m = {}
		ma = 0
		for i in range(n):
			if arr[i] not in m.keys():
				m[arr[i]] = i
			else:
				ma = max(ma, i - m[arr[i]])
		return ma


class Solution:

	def maxDistance(self, arr, n):
		mapp = {}
		maxDist = 0
		for i in range(len(arr)):
			if arr[i] not in mapp.keys():
				mapp[arr[i]] = i
			else:
				maxDist = max(maxDist, i - mapp[arr[i]])
		return maxDist


class Solution:

	def maxDistance(self, arr, n):
		list_arr = arr[::-1]
		max_val = 0
		set_arr = set(arr)
		for i in set_arr:
			val = abs(arr.index(i) - (n - 1 - list_arr.index(i)))
			if val > max_val:
				max_val = val
		return max_val


class Solution:

	def maxDistance(self, arr, n):
		maxi = 0
		d = {}
		for (i, j) in enumerate(arr):
			if j in d:
				maxi = max(maxi, i - d[j])
			else:
				d[j] = i


class Solution:

	def maxDistance(self, arr, n):
		freq = {}
		for i in range(n):
			if arr[i] not in freq:
				freq[arr[i]] = [i, -1]
			else:
				freq[arr[i]][1] = i
		m = 0
		for i in freq:
			m = max(m, freq[i][1] - freq[i][0])
		return m


class Solution:

	def maxDistance(self, arr, n):
		s = set(arr)
		m = 0
		for i in s:
			a = arr.index(i)
			b = arr[::-1].index(i)
			c = len(arr) - b - 1
			m = max(m, abs(a - c))
		return m


class Solution:

	def maxDistance(self, arr, n):
		dictt = {}
		lst = [0]
		for i in range(n):
			if arr[i] in dictt:
				lst.append(abs(dictt[arr[i]] - i))
			else:
				dictt[arr[i]] = i
		return max(lst)


class Solution:

	def maxDistance(self, arr, n):
		ans = 0
		mem = dict()
		for i in range(len(arr)):
			if arr[i] in mem:
				ans = max(ans, i - mem[arr[i]])
			else:
				mem[arr[i]] = i
		return ans


class Solution:

	def maxDistance(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = [i]
			else:
				d[arr[i]].append(i)
		m = -10 ** 7
		for i in d.values():
			i.sort()
			m = max(m, i[-1] - i[0])
		return m


import math

class Solution:

	def maxDistance(self, arr, n):
		n = len(arr)
		maxx = 0
		hash_map = dict()
		for i in range(0, n):
			if hash_map.get(arr[i], -1) == -1:
				hash_map[arr[i]] = i
			else:
				diff = i - hash_map[arr[i]]
				maxx = max(maxx, diff)
		return maxx


class Solution:

	def maxDistance(self, arr, n):
		dic = {}
		max1 = 0
		for i in range(len(arr)):
			if arr[i] not in dic:
				dic[arr[i]] = i
			else:
				max1 = max(max1, i - dic[arr[i]])
		return max1


class Solution:

	def maxDistance(self, arr, n):
		d = dict()
		m = 0
		for i in range(n):
			if arr[i] in d.keys():
				d[arr[i]][1] = i
				if d[arr[i]][1] - d[arr[i]][0] > m:
					m = d[arr[i]][1] - d[arr[i]][0]
			else:
				d[arr[i]] = [i, 0]
		return m


class Solution:

	def maxDistance(self, arr, n):
		mapp = {}
		maxdistance = 0
		for i in range(n):
			if arr[i] not in mapp:
				mapp[arr[i]] = i
			else:
				maxdistance = max(maxdistance, i - mapp[arr[i]])
		return maxdistance


class Solution:

	def maxDistance(self, arr, n):
		max_dist = 0
		hmap = {}
		for index in range(len(arr)):
			if arr[index] not in hmap:
				hmap[arr[index]] = index
			else:
				max_dist = max(max_dist, index - hmap[arr[index]])
		return max_dist


class Solution:

	def maxDistance(self, arr, n):
		hmap = {}
		for index in range(len(arr)):
			if arr[index] not in hmap:
				hmap[arr[index]] = index
		hmap2 = {}
		for index in range(n - 1, -1, -1):
			if arr[index] not in hmap2:
				hmap2[arr[index]] = index
		answer = []
		for index in range(len(arr)):
			answer.append(hmap2[arr[index]] - hmap[arr[index]])
		return max(answer)


class Solution:

	def maxDistance(self, arr, n):
		d = {}
		j = 0
		for i in arr:
			if i not in d:
				d[i] = (j, -1)
			else:
				d[i] = (d[i][0], j)
			j += 1
		mx = 0
		for i in d:
			i = d[i]
			if i[-1] != -1:
				diff = i[-1] - i[-2]
				if diff > mx:
					mx = diff
		return mx


class Solution:

	def maxDistance(self, arr, n):
		hash = dict()
		res = 0
		for (i, j) in enumerate(arr):
			if j in hash:
				res = max(res, i - hash[j])
			else:
				hash[j] = i
		return res


class Solution:

	def maxDistance(self, arr, n):
		dictt = {}
		maxx = 0
		for i in range(len(arr)):
			if arr[i] not in dictt:
				dictt[arr[i]] = i
			elif i - dictt[arr[i]] > maxx:
				maxx = i - dictt[arr[i]]
		return maxx


class Solution:

	def maxDistance(self, arr, n):
		hm = dict()
		result = 0
		for (i, val) in enumerate(arr):
			if val in hm:
				result = max(result, i - hm[val])
			else:
				hm[val] = i
		return result


class Solution:

	def maxDistance(self, arr, n):
		d = {}
		max1 = 0
		for i in range(n):
			if arr[i] in d:
				d[arr[i]][1] = i
			else:
				d[arr[i]] = [i, i]
		for (i, j) in d.items():
			max1 = max(max1, j[1] - j[0])
		return max1


class Solution:

	def maxDistance(self, arr, n):
		firstOccurence = {}
		maxD = 0
		for i in range(n):
			if arr[i] in firstOccurence:
				dist = i - firstOccurence[arr[i]]
				maxD = max(maxD, dist)
			else:
				firstOccurence[arr[i]] = i
		return maxD


from collections import defaultdict

class Solution:

	def maxDistance(self, arr, n):
		d = defaultdict()
		ans = 0
		for i in range(len(arr)):
			if arr[i] in d:
				ans = max(ans, i - d[arr[i]])
			else:
				d[arr[i]] = i
		return ans


class Solution:

	def maxDistance(self, arr, n):
		dic = {}
		maxDist = 0
		for i in range(n):
			if arr[i] in dic:
				maxDist = max(maxDist, i - dic[arr[i]])
			else:
				dic[arr[i]] = i
		return maxDist


class Solution:

	def maxDistance(self, arr, n):
		fo = {}
		maxdis = 0
		for i in range(0, len(arr)):
			if arr[i] in fo:
				dis = i - fo[arr[i]]
				maxdis = max(maxdis, dis)
			else:
				fo[arr[i]] = i
		return maxdis


class Solution:

	def maxDistance(self, arr, n):
		m = dict()
		m1 = 0
		for i in range(n):
			if arr[i] in m:
				m1 = max(m1, i - m[arr[i]])
			else:
				m[arr[i]] = i
		return m1


class Solution:

	def maxDistance(self, arr, n):
		mp = {}
		maxi = 0
		for (i, val) in enumerate(arr):
			if val in mp:
				maxi = max(maxi, i - mp[val])
			else:
				mp[val] = i
		return maxi


class Solution:

	def maxDistance(self, arr, n):
		dict = {}
		l = [0]
		for i in range(n):
			if arr[i] not in dict:
				dict[arr[i]] = i
			else:
				l.append(abs(dict[arr[i]] - i))
		return max(l)


class Solution:

	def maxDistance(self, arr, n):
		max1 = 0
		s = set(arr)
		for i in s:
			r = i
			f = arr.index(i)
			for k in range(n - 1, -1, -1):
				if arr[k] == r:
					t = k
					break
			max1 = max(max1, t - f)
		return max1


class Solution:

	def maxDistance(self, arr, n):
		maxp = {}
		maxDict = 0
		for i in range(n):
			if arr[i] not in maxp.keys():
				maxp[arr[i]] = i
			else:
				maxDict = max(maxDict, i - maxp[arr[i]])
		return maxDict


class Solution:

	def maxDistance(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] in d:
				d[arr[i]].append(i)
			else:
				d[arr[i]] = [i]
		m = 0
		for i in d:
			t = d[i][-1] - d[i][0]
			if t > m:
				m = t
		return m


class Solution:

	def maxDistance(self, arr, n):
		d = {}
		m = 0
		for (idx, i) in enumerate(arr):
			if i in d:
				m = max(idx - d[i], m)
			else:
				d[i] = idx
		return m


class Solution:

	def maxDistance(self, arr, n):
		d = {}
		m = 0
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = i
			elif i - d[arr[i]] > m:
				m = i - d[arr[i]]
		return m


class Solution:

	def maxDistance(self, arr, n):
		d = {}
		x = 0
		for i in arr:
			if i not in d:
				d[i] = [x]
			else:
				d[i].append(x)
			x = x + 1
		res = -1
		for i in d:
			e = d[i][len(d[i]) - 1] - d[i][0]
			if e > res:
				res = e
		return res


class Solution:

	def maxDistance(self, arr, n):
		maximum = 0
		dict1 = dict()
		for i in range(n):
			if arr[i] not in dict1:
				dict1[arr[i]] = i
			else:
				maximum = max(maximum, i - dict1[arr[i]])
		return maximum


class Solution:

	def maxDistance(self, arr, n):
		s = set(arr)
		max1 = -10 ** 9
		for i in s:
			first = arr.index(i)
			last = n - 1 - arr[::-1].index(i)
			if abs(last - first) > max1:
				max1 = abs(last - first)
		return max1


class Solution:

	def maxDistance(self, arr, n):
		d1 = {}
		d2 = {}
		for i in range(len(arr)):
			if arr[i] not in d1:
				d1[arr[i]] = i
				d2[arr[i]] = 0
			else:
				d2[arr[i]] = max(d2[arr[i]], i - d1[arr[i]])
		max1 = -1
		for key in d2:
			max1 = max(max1, d2[key])
		return max1


class Solution:

	def maxDistance(self, arr, n):
		dict1 = {}
		for (i, a) in enumerate(arr):
			if a not in dict1.keys():
				dict1[a] = [i]
			else:
				dict1[a].append(i)
		max1 = 0
		for i in dict1.values():
			max1 = max(max1, i[-1] - i[0])
		return max1


class Solution:

	def maxDistance(self, arr, n):
		ans = 0
		m = max(arr) + 1
		maxi = [-1 for i in range(m)]
		for i in range(n):
			if maxi[arr[i]] == -1:
				maxi[arr[i]] = i
			else:
				ans = max(ans, i - maxi[arr[i]])
		return ans


class Solution:

	def maxDistance(self, arr, n):
		rarr = arr[::-1]
		maxd = 0
		for (i, num) in enumerate(arr):
			dist = 0
			ind = n - rarr.index(num) - 1
			dist = abs(ind - i)
			maxd = max(maxd, dist)
		return maxd


class Solution:

	def maxDistance(self, arr, n):
		m = 0
		a = arr[::-1]
		s = set(a)
		for i in s:
			if m < abs(arr.index(i) - (len(arr) - a.index(i) - 1)):
				m = abs(arr.index(i) - (len(arr) - a.index(i) - 1))
		return m


class Solution:

	def maxDistance(self, arr, n):
		l = []
		for i in arr:
			if i not in l:
				l.append(i)
		maxx = 0
		for i in l:
			maxx = max(maxx, n - arr[::-1].index(i) - 1 - arr.index(i))
		return maxx


class Solution:

	def maxDistance(self, arr, n):
		df = {}
		dl = {}
		for i in range(n):
			if arr[i] not in df:
				df[arr[i]] = i
				dl[arr[i]] = i
			else:
				dl[arr[i]] = i
		ans = 0
		for i in arr:
			ans = max(ans, dl[i] - df[i])
		return ans


class Solution:

	def maxDistance(self, arr, n):
		max_d = 0
		first_pos = dict()
		for index in range(n):
			if arr[index] in first_pos:
				max_d = max(max_d, index - first_pos[arr[index]])
			else:
				first_pos[arr[index]] = index
		return max_d


class Solution:

	def maxDistance(self, arr, n):
		maxdis = 0
		freq = {}
		for i in range(n):
			if arr[i] not in freq.keys():
				freq[arr[i]] = i
			else:
				maxdis = max(maxdis, i - freq[arr[i]])
		return maxdis