CodeMart is a shopping platform and it is distributing gift vouchers to its esteemed users. The voucher can be redeemed by providing a fixed amount of shopping credits to the platform. One credit is sent by a user to the platform by doing one occurance in CodeMart. Since there is a huge rush of people you are required to manage the users on the basis of first come first serve. The user which came first and has exactly k occurrences at last is given the voucher first. You are given an array arr[ ] with the id's of N users in chronological order of their occurances . You are required to print the id of the user which will be given the voucher first. If no such user meets the condition print "-1".
Example 1:
Input:
N = 7 
K = 2
arr[] = {1, 7, 4, 3, 4, 8, 7} 
Output: 7
Explanation: Both 7 and 4 occur 2 times.
But 7 is the first that occurs 2 times.  
Example 2:
Input:
N = 6 
K = 1 
arr[] = {4, 1, 6, 1, 6, 4} 
Output: -1 
Explanation: No one occurs exactly 1 time.
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function firstElement() that takes array arr, integer n and integer k as input parameters and returns the required answer.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(max(arr[i])).
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ arr[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def firstElement(self, arr, n, k): 



Solutions:
from collections import Counter

class Solution:

	def firstElement(self, arr, n, k):
		c = Counter(arr)
		for i in arr:
			if c[i] == k:
				return i
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		if k == 0:
			return -1
		count = {}
		for ele in arr:
			if ele in count:
				count[ele] += 1
			else:
				count[ele] = 1
		for ele in arr:
			if count[ele] == k:
				return ele
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		mx = 0
		for i in arr:
			if i > mx:
				mx = i
		tab = [0 for i in range(0, mx + 1)]
		for i in arr:
			tab[i] += 1
		val = []
		for i in range(len(tab)):
			if tab[i] == k:
				val.append(i)
		for i in arr:
			if i in val:
				return i
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		a = []
		d = dict()
		for i in arr:
			d[i] = 0
		for i in arr:
			d[i] = d[i] + 1
		for i in arr:
			if d[i] == k:
				return i
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		d = dict()
		for ele in arr:
			d[ele] = 0
		for ele in arr:
			d[ele] = d[ele] + 1
		for ele in arr:
			if d[ele] == k:
				return ele
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		idc = {}
		for i in arr:
			if i in idc:
				idc[i] += 1
			else:
				idc[i] = 1
		for i in arr:
			if idc[i] == k:
				return i
		return -1


class Solution:

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


class Solution:

	def firstElement(self, arr, n, k):
		dict_ = {}
		ind = n
		for elem in arr:
			dict_.update({elem: dict_.get(elem, 0) + 1})
		res = [key for (key, value) in dict_.items() if value == k]
		p = sorted(set(res), key=arr.index)
		return p[0] if p else -1


class Solution:

	def firstElement(self, arr, n, k):
		freq = {}
		for i in range(n):
			if arr[i] not in freq:
				freq[arr[i]] = [i, 1]
			else:
				freq[arr[i]][1] += 1
		mi = 100000000.0
		for i in freq:
			if freq[i][1] == k and mi > freq[i][0]:
				mi = freq[i][0]
		if mi == 100000000.0:
			return -1
		return arr[mi]


class Solution:

	def firstElement(self, arr, n, k):
		hash = {}
		for i in range(len(arr)):
			if arr[i] in hash:
				hash[arr[i]] += 1
			else:
				hash[arr[i]] = 1
		for i in range(len(arr)):
			if hash[arr[i]] == k:
				return arr[i]
		return -1


class Solution:

	def firstElement(self, A, n, k):
		from collections import Counter
		d = Counter(A)
		for i in A:
			if d[i] == k:
				return i
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		s = {}
		for i in arr:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		ans = []
		for i in s:
			if s[i] == k:
				ans.append(i)
		ans = set(ans)
		for i in range(n):
			if arr[i] in ans:
				return arr[i]
				break
		return -1


import collections

class Solution:

	def firstElement(self, arr, n, k):
		x = collections.Counter(arr)
		for i in range(n):
			if x[arr[i]] == k:
				return arr[i]
		return -1


from collections import Counter

class Solution:

	def firstElement(self, arr, n, k):
		di = dict(Counter(arr))
		d = {}
		for (i, j) in enumerate(arr):
			if j not in d:
				d[j] = i
		ans = []
		for (i, j) in di.items():
			if j == k:
				ans.append(i)
		for i in arr:
			if i in ans:
				return i
		return '-1'


class Solution:

	def firstElement(self, arr, n, k):
		D = {}
		for i in arr:
			if i in D:
				D[i] += 1
			else:
				D[i] = 1
		L = [i for (i, v) in D.items() if v == k]
		if L:
			for i in arr:
				if i in L:
					return i
		return -1


from collections import OrderedDict

class Solution:

	def firstElement(self, a, n, k):
		d = OrderedDict()
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] == k:
				return i
		return -1


class Solution:

	def firstElement(self, arr, n, k1):
		d = {}
		a = []
		dic = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (k, v) in d.items():
			if v == k1:
				if k not in dic:
					dic[k] = k
		if len(dic) == 0:
			return -1
		else:
			for i in arr:
				if i in dic.values():
					return i


from collections import defaultdict

class Solution:

	def firstElement(self, arr, n, k):
		def_d = defaultdict()
		a = []
		for i in arr:
			if i in def_d:
				def_d[i] += 1
			else:
				def_d[i] = 1
		for i in arr:
			if def_d[i] == k:
				a.append(i)
		if len(a) > 0:
			return a[0]
		else:
			return -1


class Solution:

	def firstElement(self, arr, n, k):
		count = [0] * 1001
		index = [-1] * 1001
		for i in range(n):
			if index[arr[i]] == -1:
				index[arr[i]] = i
			count[arr[i]] += 1
		first = 10001
		for i in range(1001):
			if count[i] == k:
				first = min(first, index[i])
		if first == 10001:
			return -1
		else:
			return arr[first]


class Solution:

	def firstElement(self, arr, n, k):
		counts = {}
		for x in arr:
			if x not in counts:
				counts[x] = 1
			else:
				counts[x] += 1
		for x in arr:
			if counts[x] == k:
				return x
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		dic = {}
		for i in range(n):
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
		s = []
		for (i, j) in dic.items():
			if j == k:
				s.append(i)
		if len(s) == 0:
			return -1
		minIdx = arr.index(s[0])
		for i in s:
			if arr.index(i) < minIdx:
				minIdx = arr.index(i)
		return arr[minIdx]


class Solution:

	def firstElement(self, arr, n, k):
		dict = {}
		Arr = []
		for i in range(n):
			if arr[i] not in dict:
				dict[arr[i]] = 1
			else:
				dict[arr[i]] += 1
		for i in dict:
			if dict[i] == k:
				Arr.append(i)
		for i in range(n):
			if arr[i] in Arr:
				return arr[i]
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		count_map = {}
		for i in range(0, n):
			if arr[i] in count_map.keys():
				count_map[arr[i]] += 1
			else:
				count_map[arr[i]] = 1
			i += 1
		for i in range(0, n):
			if count_map[arr[i]] == k:
				return arr[i]
			i += 1
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		freq = {}
		for i in range(0, n):
			if arr[i] in freq:
				freq[arr[i]] += 1
			else:
				freq[arr[i]] = 1
		res = []
		for (e, v) in freq.items():
			if v == k:
				res.append(e)
		if len(res) != 0:
			for i in range(0, n):
				if arr[i] in res:
					return arr[i]
		return -1


from collections import Counter

class Solution:

	def firstElement(self, arr, n, k):
		table = Counter(arr)
		for elem in arr:
			if table[elem] == k:
				return elem
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		table = {}
		for i in arr:
			table[i] = table.get(i, 0) + 1
		for elem in arr:
			if table[elem] == k:
				return elem
		return -1


from collections import Counter as c

class Solution:

	def firstElement(self, arr, n, k):
		table = {}
		for i in arr:
			table[i] = table.get(i, 0) + 1
		for elem in arr:
			if table[elem] == k:
				return elem
		return -1


from collections import Counter

class Solution:

	def firstElement(self, arr, n, k):
		py_dict = Counter(arr)
		for item in arr:
			if py_dict[item] == k:
				return item
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		lst = [0] * (max(arr) + 1)
		for i in arr:
			lst[i] += 1
		for i in arr:
			if lst[i] == k:
				return i
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		table = {}
		for i in arr:
			if i in table:
				table[i] += 1
			else:
				table[i] = 1
		key_index = -1
		for key in table:
			if table[key] == k:
				if key_index is -1 or key_index > arr.index(key):
					key_index = arr.index(key)
		if key_index >= 0:
			return arr[key_index]
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		d = {}
		ans = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] == k:
				ans.append([i, arr.index(i)])
		if len(ans) == 0:
			return -1
		else:
			MinIdx = float('inf')
			MinVal = 0
			for (i, j) in ans:
				if j < MinIdx:
					MinIdx = j
					MinVal = i
			return MinVal


class Solution:

	def firstElement(self, arr, n, k):
		count = [0] * 1000
		for num in arr:
			count[num - 1] += 1
		for num in arr:
			if count[num - 1] == k:
				return num
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		a = [0] * (max(arr) + 1)
		for j in arr:
			a[j] += 1
		for j in arr:
			if a[j] == k:
				return j
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		H = {}
		idx = 0
		for i in range(n):
			H[arr[i]] = H.get(arr[i], 0) + 1
		for j in range(n):
			if H[arr[j]] == k:
				return arr[j]
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		di = {}
		for i in arr:
			di[i] = di.get(i, 0) + 1
		for i in range(n):
			if di[arr[i]] == k:
				return arr[i]
		return -1


from collections import OrderedDict

class Solution:

	def firstElement(self, arr, n, k):
		o = OrderedDict()
		for item in arr:
			if item in o:
				o[item] += 1
			else:
				o[item] = 1
		for item in o:
			if o[item] == k:
				return item
		return -1


class Solution:

	def firstElement(self, a, n, k):
		m = {}
		for i in range(n):
			if a[i] not in m.keys():
				m[a[i]] = 1
			else:
				m[a[i]] += 1
		for i in range(n):
			if m[a[i]] == k:
				return a[i]
		else:
			return -1


from collections import Counter

class Solution:

	def firstElement(self, arr, n, k):
		m = Counter(arr)
		l = []
		for (keys, values) in m.items():
			if values == k:
				l.append(keys)
		if l:
			for i in arr:
				if i in l:
					return i
		else:
			return -1


from collections import Counter

class Solution:

	def firstElement(self, arr, n, k):
		cnt = Counter(arr)
		for val in arr:
			if cnt[val] == k:
				return val
		return -1


class Solution:

	def firstElement(self, arr: list, n: int, k: int) -> int:
		counter = {}
		for i in range(n):
			if arr[i] in counter:
				counter[arr[i]] += 1
			else:
				counter[arr[i]] = 1
		for i in range(n):
			if counter[arr[i]] == k:
				return arr[i]
		return -1


from collections import Counter

class Solution:

	def firstElement(self, arr, n, k):
		count = Counter(arr)
		for i in range(0, n):
			if count[arr[i]] == k:
				return arr[i]
		return -1


class Solution:

	def firstElement(self, arr, n, k):
		hashmap = {}
		for num in arr:
			hashmap[num] = hashmap.get(num, 0) + 1
		for num in arr:
			if hashmap[num] == k:
				return num
		return -1


from collections import Counter

class Solution:

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


class Solution:

	def firstElement(self, arr, n, k):
		dic = {}
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		for i in arr:
			if dic[i] == k:
				return i
		return -1