Given an array arr[] of size n, find the first repeating element. The element should occur more than once and the index of its first occurrence should be the smallest.
Note:- The position you return should be according to 1-based indexing. 
Example 1:
Input:
n = 7
arr[] = {1, 5, 3, 4, 3, 5, 6}
Output: 2
Explanation: 
5 is appearing twice and 
its first appearence is at index 2 
which is less than 3 whose first 
occuring index is 3.
Example 2:
Input:
n = 4
arr[] = {1, 2, 3, 4}
Output: -1
Explanation: 
All elements appear only once so 
answer is -1.
Your Task:
You don't need to read input or print anything. Complete the function firstRepeated() which takes arr and n as input parameters and returns the position of the first repeating element. If there is no such element, return -1.
 
Expected Time Complexity: O(n)
Expected Auxilliary Space: O(n)
 
Constraints:
1 <= n <= 10^{6}
0 <= A_{i}<= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    #Function to return the position of the first repeating element.

    def firstRepeated(self,arr, n):

        

        #arr : given array

        #n : size of the array

Solutions:
class Solution:

	def firstRepeated(self, arr, n):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in range(len(arr)):
			if d[arr[i]] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		from collections import OrderedDict
		dic = OrderedDict()
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		for i in dic:
			if dic[i] > 1:
				return arr.index(i) + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		dicto = dict()
		for i in range(n):
			if arr[i] in dicto:
				dicto[arr[i]] += 1
			else:
				dicto[arr[i]] = 1
		for i in arr:
			if dicto[i] >= 2:
				return arr.index(i) + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		for i in range(n):
			if arr[i] in arr[i + 1:n]:
				return i + 1
				break
			elif len(arr) == len(set(arr)):
				return -1


class Solution:

	def firstRepeated(self, arr, n):
		hash = {}
		for i in range(n):
			if arr[i] in hash.keys():
				hash[arr[i]] += 1
			else:
				hash[arr[i]] = 1
		for i in range(n):
			if hash[arr[i]] >= 2:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		list = []
		seen = {}
		for (i, num) in enumerate(arr):
			if num in seen:
				list.append(seen[num])
			seen[num] = i + 1
		if len(list) == 0:
			return -1
		else:
			return min(list)


class Solution:

	def firstRepeated(self, arr, n):
		min = -1
		d = dict()
		for i in range(n - 1, -1, -1):
			if arr[i] in d.keys():
				min = i
			else:
				d[arr[i]] = 1
		if min != -1:
			return min + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		from collections import Counter
		d = Counter(arr)
		for i in range(n):
			if d[arr[i]] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		data_map = {}
		ans = n + 1
		for i in range(n):
			if data_map.get(arr[i]):
				ans = min(ans, data_map.get(arr[i]))
			else:
				data_map[arr[i]] = i + 1
		return ans if ans != n + 1 else -1


class Solution:

	def firstRepeated(self, arr, n):
		dict_ = {}
		ans = {}
		for i in range(n):
			if arr[i] in dict_:
				ans[arr[i]] = dict_[arr[i]] + 1
			else:
				dict_[arr[i]] = i
		return min(ans.values()) if ans else -1


class Solution:

	def firstRepeated(self, arr, n):
		hash = {}
		for ele in arr:
			if ele not in hash:
				hash[ele] = 1
			else:
				hash[ele] += 1
		for i in range(n):
			if hash[arr[i]] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		set1 = set(arr)
		if len(set1) != n:
			for i in arr:
				if arr.count(i) > 1:
					temp = arr.index(i) + 1
					break
			return temp
		else:
			return -1


class Solution:

	def firstRepeated(self, arr, n):
		rep = {}
		min_ind = 1000000.0 + 1
		for i in range(n):
			if arr[i] in rep:
				rep[arr[i]] = min(rep[arr[i]], i)
				min_ind = min(min_ind, rep[arr[i]])
			else:
				rep[arr[i]] = i
		if min_ind == 1000000.0 + 1:
			return -1
		return min_ind + 1


class Solution:

	def firstRepeated(self, arr, n):
		dic = dict()
		for i in range(len(arr)):
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
		d = {k: v for (k, v) in dic.items() if v > 1}
		for i in range(len(arr)):
			if arr[i] in d:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		ind = dict()
		small_ind = -1
		for i in range(n):
			if arr[i] in ind:
				if small_ind == -1 or small_ind > ind[arr[i]]:
					small_ind = ind[arr[i]] + 1
				ind[arr[i]] = i
			else:
				ind[arr[i]] = i
		return small_ind


class Solution:

	def firstRepeated(self, arr, n):
		count = {}
		for i in range(n):
			if arr[i] in count:
				count[arr[i]] = count[arr[i]] + 1
			else:
				count[arr[i]] = 1
		for j in range(n):
			if count[arr[j]] > 1:
				return j + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		dict_count = {}
		out_ind = n
		for i in range(n):
			if arr[i] in dict_count.keys():
				if len(dict_count[arr[i]]) < 2:
					dict_count[arr[i]].append(i)
			else:
				dict_count[arr[i]] = [i]
		count = 0
		for keys in dict_count:
			if len(dict_count[keys]) > 1:
				index = dict_count[keys][0]
				out_ind = min(index, out_ind)
			if len(dict_count[keys]) == 1:
				count += 1
		if count == n:
			return -1
		else:
			return out_ind + 1


class Solution:

	def firstRepeated(self, arr, n):
		d = {}
		m = n
		for _ in range(len(arr)):
			if arr[_] not in d:
				d[arr[_]] = _
			elif d[arr[_]] < m:
				m = d[arr[_]]
		if 0 <= m < n:
			return m + 1
		else:
			return -1


class Solution:

	def firstRepeated(self, arr, n):
		sets = set(arr)
		if len(sets) == len(arr):
			return -1
		for val in arr:
			if arr.count(val) > 1:
				return arr.index(val) + 1


class Solution:

	def firstRepeated(self, arr, n):
		d = {}
		idx = n
		for i in range(n):
			if arr[i] in d:
				temp = d[arr[i]]
				if temp < idx:
					idx = temp
			else:
				d[arr[i]] = i
		if idx == n:
			return -1
		return idx + 1


class Solution:

	def firstRepeated(self, arr, n):
		num_dict = {}
		min_index = n
		for i in range(n):
			if arr[i] not in num_dict:
				num_dict[arr[i]] = i
			else:
				min_index = min(min_index, num_dict[arr[i]])
		return min_index + 1 if min_index != n else -1


class Solution:

	def firstRepeated(self, arr, n):
		freq = {}
		for i in range(n):
			if arr[i] not in freq:
				freq[arr[i]] = 1
			else:
				freq[arr[i]] += 1
		for i in range(n):
			if freq[arr[i]] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		d = {}
		sol = n
		flag = False
		for i in range(n):
			if arr[i] in d:
				if sol > d[arr[i]]:
					sol = d[arr[i]]
				flag = True
			else:
				d[arr[i]] = i
		if flag:
			return sol + 1
		else:
			return -1


class Solution:

	def firstRepeated(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		for i in arr:
			if d[i] >= 2:
				return arr.index(i) + 1
				break
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		d = {}
		m = 1000000000
		for i in range(n):
			try:
				m = min(m, d[arr[i]])
			except:
				d.__setitem__(arr[i], i + 1)
		if m == 1000000000:
			return -1
		return m


from collections import OrderedDict

class Solution:

	def firstRepeated(self, arr, n):
		ans = 9999999999999
		d = dict()
		for (i, e) in enumerate(arr):
			if e in d:
				if d[e] < ans and ans != -1:
					ans = d[e]
			else:
				d[e] = i
		if ans != 9999999999999:
			return ans + 1
		else:
			return -1


class Solution:

	def firstRepeated(self, arr, n):
		freq = {}
		for i in arr:
			try:
				freq[i] += 1
			except:
				freq[i] = 1
		for i in range(n):
			if freq[arr[i]] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		dict1 = {}
		minn = -1
		for i in range(n - 1, -1, -1):
			if arr[i] in dict1:
				minn = i + 1
			else:
				dict1[arr[i]] = 1
		return minn


class Solution:

	def firstRepeated(self, arr, n):
		s = dict()
		s[arr[0]] = 1
		x = []
		for i in range(1, n):
			if arr[i] in s:
				x.append(s[arr[i]])
			else:
				s[arr[i]] = i + 1
		x.sort()
		return x[0] if len(x) > 0 else -1


class Solution:

	def firstRepeated(self, arr, n):
		hat = {}
		for i in range(n):
			if arr[i] in hat:
				hat[arr[i]] += 1
			else:
				hat[arr[i]] = 1
		for i in arr:
			if hat[i] > 1:
				return arr.index(i) + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		res = {}
		for i in arr:
			if i in res:
				res[i] += 1
			else:
				res[i] = 1
		for i in range(n):
			if res[arr[i]] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		m = {}
		ans = 1000000000.0
		for i in range(n):
			if arr[i] not in m:
				m[arr[i]] = i
			else:
				ans = min(ans, m[arr[i]] + 1)
		return -1 if ans == 1000000000.0 else ans


class Solution:

	def firstRepeated(self, arr, n):
		hashset = set()
		min_index = float('inf')
		for i in range(n - 1, -1, -1):
			if arr[i] in hashset:
				min_index = i + 1
			hashset.add(arr[i])
		if min_index != float('inf'):
			return min_index
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		tmp = -1
		for i in arr:
			if i in d and d[i] >= 2:
				tmp = i
				break
		if tmp == -1:
			return -1
		for i in range(n):
			if arr[i] == tmp:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		freq = {}
		mini = float('inf')
		for i in range(n):
			if arr[i] not in freq:
				freq[arr[i]] = i + 1
			else:
				mini = min(mini, freq[arr[i]])
		if mini == float('inf'):
			return -1
		return mini


class Solution:

	def firstRepeated(self, arr, n):
		if n == 0 or n == 1:
			return -1
		hashmap = {}
		min_repeating_index = n + 1
		for i in range(n):
			if arr[i] in hashmap:
				if min_repeating_index > hashmap[arr[i]]:
					min_repeating_index = hashmap[arr[i]]
			else:
				hashmap[arr[i]] = i
		return -1 if min_repeating_index == n + 1 else min_repeating_index + 1


from collections import Counter

class Solution:

	def firstRepeated(self, arr, n):
		d = Counter(arr)
		for (k, v) in enumerate(arr):
			if d[v] > 1:
				return k + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		dic = {}
		flag = False
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		for j in arr:
			if dic[j] >= 2:
				flag = True
				return arr.index(j) + 1
		if flag == False:
			return -1


class Solution:

	def firstRepeated(self, arr, n):
		s = set()
		ans = -1
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] in s:
				ans = i
			else:
				s.add(arr[i])
		if ans == -1:
			return -1
		else:
			return ans + 1


class Solution:

	def firstRepeated(self, arr, n):
		count = dict()
		for i in arr:
			if i not in count:
				count[i] = 1
			else:
				count[i] += 1
		for i in range(n):
			if count[arr[i]] != 1:
				return i + 1
		return -1


from collections import *

class Solution:

	def firstRepeated(self, arr, n):
		d = defaultdict(int)
		for i in arr:
			d[i] += 1
		for i in range(0, n - 1):
			if d[arr[i]] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		dict = {}
		for i in arr:
			if i not in dict:
				dict[i] = 1
			else:
				dict[i] += 1
		for i in arr:
			if dict[i] > 1:
				return arr.index(i) + 1
		return -1


from collections import Counter

class Solution:

	def firstRepeated(self, arr, n):
		counter = Counter(arr)
		for (i, x) in enumerate(arr):
			if counter[x] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		dicti = {}
		for i in range(0, n):
			if arr[i] in dicti:
				dicti[arr[i]] += 1
			else:
				dicti[arr[i]] = 1
		for i in range(0, n):
			if dicti[arr[i]] > 1:
				return i + 1
		else:
			return -1


class Solution:

	def firstRepeated(self, arr, n):
		smallest_index = 1000000
		tic = 0
		counter = {}
		for i in range(n):
			if arr[i] not in counter:
				counter[arr[i]] = [i, 1]
			else:
				counter[arr[i]][1] += 1
		for (key, val) in counter.items():
			if val[1] > 1:
				smallest_index = min(smallest_index, val[0])
		if smallest_index == 1000000:
			return -1
		return smallest_index + 1


class Solution:

	def firstRepeated(self, arr, n):
		hash = {}
		for i in arr:
			hash[i] = hash.get(i, 0) + 1
		for i in range(len(arr)):
			if hash[arr[i]] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		dict = {}
		for i in range(n):
			try:
				dict[arr[i]] += 1
			except KeyError:
				dict[arr[i]] = 1
		for i in range(n):
			if dict[arr[i]] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		freq = {}
		for i in range(n):
			if arr[i] in freq:
				freq[arr[i]]['count'] += 1
			else:
				freq[arr[i]] = {'count': 1, 'index': i}
		min_index = n + 1
		for key in freq:
			if freq[key]['count'] > 1 and freq[key]['index'] < min_index:
				min_index = freq[key]['index']
		if min_index == n + 1:
			return -1
		else:
			return min_index + 1


class Solution:

	def firstRepeated(self, arr, n):
		ds = {}
		max = -1
		for i in range(n):
			if arr[i] in ds:
				if max == -1:
					max = ds[arr[i]]
				elif ds[arr[i]] < max:
					max = ds[arr[i]]
				else:
					max = max
			else:
				ds[arr[i]] = i + 1
		return max


import collections

class Solution:

	def firstRepeated(self, arr, n):
		ans = -1
		x = collections.Counter(arr)
		for (i, j) in enumerate(arr):
			if x[j] > 1:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		max_val = max(arr)
		index = {}
		for i in range(n):
			if arr[i] not in index:
				index[arr[i]] = i
		hash = [0] * (max_val + 1)
		for i in range(n):
			hash[arr[i]] += 1
		repeating = float('inf')
		for i in range(n):
			if hash[arr[i]] > 1:
				repeating = arr[i]
				break
		if repeating == float('inf'):
			return -1
		else:
			return index[repeating] + 1


class Solution:

	def firstRepeated(self, arr, n):
		freq = [0] * (10 ** 6 + 1)
		for num in arr:
			freq[num] += 1
		for i in range(n):
			if freq[arr[i]] >= 2:
				return i + 1
		return -1


class Solution:

	def firstRepeated(self, arr, n):
		ans = 10 ** 6
		mp = dict()
		for i in range(n):
			if arr[i] not in mp:
				mp[arr[i]] = i
			else:
				ans = min(ans, mp[arr[i]] + 1)
		if ans == 10 ** 6:
			return -1
		else:
			return ans


from collections import Counter

class Solution:

	def firstRepeated(self, arr, n):
		myset = set()
		ans = -1
		for i in range(n - 1, -1, -1):
			if arr[i] in myset:
				ans = i
			else:
				myset.add(arr[i])
		if ans == -1:
			return -1
		else:
			return ans + 1