Given an array of n integers. Find the kth distinct element.
Example 1:
Input: 
n = 6, k = 2
arr = {1, 2, 1, 3, 4, 2}
Output:
4
Explanation: 1st distinct element will be 3
and the 2nd distinct element will be 4. As 
both the elements present in the array only 1 
times.
Example 2:
Input: 
n = 6, k = 3
arr = {1, 2, 50, 10, 20, 2}
Output:
10
Your Task:
You don't need to read or print anything. Your task is to complete the function KthDistinct() which takes the array of elements as input parameter and returns the kth distinct element. If not possible return -1.
Expected Time Complexity: O(n)
Expected Space Complexity: O(n)
Constranits:
1 <= length of array <= 10^{5}
1 <= elements of array <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

	def KthDistinct(self, nums, k):

		# Code here

Solutions:
class Solution:

	def KthDistinct(self, nums, k):
		dict = {}
		for i in range(len(nums)):
			if nums[i] not in dict:
				dict[nums[i]] = 1
			else:
				dict[nums[i]] += 1
		for i in range(len(nums)):
			if dict[nums[i]] > 1:
				continue
			else:
				k = k - 1
			if k == 0:
				return nums[i]
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		freq = {}
		for i in nums:
			if i not in freq:
				freq[i] = 0
			freq[i] += 1
		for i in nums:
			if freq[i] == 1:
				k -= 1
				if not k:
					return i
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		d = {}
		for i in nums:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		v = []
		for i in nums:
			if d[i] == 1:
				v.append(i)
		if not v or len(v) < k:
			return -1
		return v[k - 1]


from collections import Counter

class Solution:

	def KthDistinct(self, arr, k):
		dict = {}
		vect = []
		size = len(nums)
		for i in range(size):
			if arr[i] in dict:
				dict[arr[i]] = dict[arr[i]] + 1
			else:
				dict[arr[i]] = 1
		for i in range(size):
			if dict[arr[i]] > 1:
				continue
			else:
				k = k - 1
			if k == 0:
				return arr[i]
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		dic = {}
		lis = []
		for i in nums:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		j = 0
		for i in nums:
			if dic[i] == 1:
				j += 1
				if j == k:
					return i
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		m = max(nums) + 1
		mp = [0 for i in range(m)]
		for i in nums:
			mp[i] += 1
		for i in range(n):
			if mp[nums[i]] == 1:
				k -= 1
				if k == 0:
					return nums[i]
			else:
				k = k
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		store = {}
		count = 0
		for i in range(len(nums)):
			if nums[i] not in store:
				store[nums[i]] = 1
			elif nums[i] in store:
				store[nums[i]] += 1
		for i in range(len(nums)):
			if store[nums[i]] > 1:
				continue
			else:
				k = k - 1
			if k == 0:
				return nums[i]
		return -1


from collections import OrderedDict

class Solution:

	def KthDistinct(self, nums, k):
		o = OrderedDict()
		for item in nums:
			if item in o:
				o[item] += 1
			else:
				o[item] = 1
		count = 0
		for item in o:
			count += o[item] == 1
			if count == k:
				return item
		return -1


class Solution:

	def KthDistinct(self, nums, K):
		dict = {}
		for i in nums:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		j = 0
		for i in nums:
			if dict[i] == 1:
				j += 1
				if j == k:
					return i
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		d = {}
		for i in range(len(nums)):
			if nums[i] not in d:
				d[nums[i]] = [i]
			else:
				d[nums[i]].append(i)
		d2 = {}
		for i in d:
			if len(d[i]) == 1:
				d2[d[i][0]] = i
		m = sorted(d2.keys())
		if len(m) >= k:
			a = m[k - 1]
			return d2[a]
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		Hash = dict()
		for i in range(len(nums)):
			Hash[nums[i]] = Hash.get(nums[i], 0) + 1
		count = 0
		for i in nums:
			if Hash[i] == 1:
				count += 1
			if count == k:
				return i
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		s = {}
		for i in nums:
			s[i] = s.get(i, 0) + 1
		count = 0
		for i in nums:
			if s[i] == 1:
				count = count + 1
			if count == k:
				return i
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		d = {}
		c = 0
		if k > len(nums):
			return -1
		for i in nums:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in nums:
			if d[i] == 1 and c < k:
				c += 1
				if c == k:
					return i
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		d = {}
		cnt = 0
		for ele in nums:
			if ele not in d.keys():
				d[ele] = 1
			else:
				d[ele] += 1
		for el in nums:
			if d[el] == 1:
				cnt += 1
				if cnt == k:
					return el
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		l = [0] * (max(nums) + 1)
		freq = 0
		for i in nums:
			l[i] += 1
		for i in nums:
			if l[i] == 1:
				freq += 1
			if freq == k:
				return i
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		d = {}
		for itr in range(len(nums)):
			if nums[itr] in d.keys():
				d[nums[itr]] += 1
			else:
				d[nums[itr]] = 1
		count = 0
		for itr in range(len(nums)):
			if d[nums[itr]] == 1:
				count += 1
			if count == k:
				return nums[itr]
		return -1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.KthDistinct(nums, k)
		print(ans)


class Solution:

	def KthDistinct(self, nums, k):
		s = {}
		for i in nums:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		c = 0
		for i in nums:
			if s[i] == 1:
				c += 1
				if c == k:
					return i
		return -1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.KthDistinct(nums, k)
		print(ans)


class Solution:

	def KthDistinct(self, nums, k):
		d = {}
		for i in nums:
			d[i] = d.get(i, 0) + 1
		li = []
		for i in nums:
			li.append(d.get(i))
		min1 = min(li)
		count = 0
		for i in nums:
			if count <= k:
				if d.get(i) == min1:
					count += 1
				if count == k:
					return i
		return -1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.KthDistinct(nums, k)
		print(ans)


import heapq

class Solution:

	def KthDistinct(self, nums, k):
		dc = {}
		idx = 0
		for i in nums:
			if i in dc.keys():
				dc[i][1] = dc[i][1] + 1
			else:
				dc[i] = [idx, 1]
			idx = idx + 1
		heap = [(val[0], key) for (key, val) in dc.items() if val[1] == 1]
		smal = heapq.nsmallest(k, heap)
		if len(smal) >= k:
			rslt = smal[k - 1][1]
		else:
			rslt = -1
		return rslt
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.KthDistinct(nums, k)
		print(ans)


class Solution:

	def KthDistinct(self, nums, k):
		Map = {}
		for i in nums:
			Map[i] = 1 + Map.get(i, 0)
		cnt = 0
		for i in nums:
			if Map[i] == 1:
				cnt += 1
				if cnt == k:
					return i
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		d = {}
		for i in nums:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in nums:
			if d[i] == 1:
				k -= 1
				if k == 0:
					return i
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		from collections import OrderedDict
		x = OrderedDict.fromkeys(nums, 0)
		for i in nums:
			x[i] += 1
		t = 1
		for i in x.keys():
			if x[i] == 1:
				if t == k:
					return i
				t += 1
		else:
			return -1


class Solution:

	def KthDistinct(self, nums, k):
		dict_ = {}
		for i in range(len(nums)):
			if nums[i] not in dict_:
				dict_[nums[i]] = 1
			else:
				dict_[nums[i]] += 1
		cnt = 0
		for numi in nums:
			if dict_[numi] == 1:
				cnt += 1
			if cnt == k:
				return numi
		return -1


from collections import defaultdict

class Solution:

	def KthDistinct(self, nums, k):
		h = defaultdict(int)
		count = 0
		for i in range(0, len(nums)):
			h[nums[i]] += 1
		for i in range(0, len(nums)):
			if h[nums[i]] == 1:
				count += 1
			if count == k:
				return nums[i]
		return -1


class Solution:

	def KthDistinct(self, nums, k):
		L = []
		D = {}
		for i in nums:
			if D.get(i) != None:
				D[i] += 1
			else:
				D[i] = 1
		for i in nums:
			if D[i] == 1:
				L.append(i)
		if k <= len(L):
			return L[k - 1]
		else:
			return -1


class Solution:

	def KthDistinct(self, nums, k):
		a = []
		from collections import defaultdict
		count = defaultdict(int)
		for i in nums:
			count[i] += 1
		for i in nums:
			if count[i] == 1:
				a.append(i)
		if len(a) < k:
			return -1
		return a[k - 1]


class Solution:

	def KthDistinct(self, nums, k):
		s = {}
		for i in nums:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		c = 0
		for i in nums:
			if s[i] == 1:
				c += 1
			if c == k:
				return i
		return -1


from collections import Counter

class Solution:

	def KthDistinct(self, nums, k):
		k_count = 0
		c = Counter(nums)
		for num in nums:
			if c[num] == 1:
				k_count += 1
				if k == k_count:
					return num
		return -1


class Solution:

	def KthDistinct(self, arr, KthIndex):
		dict = {}
		vect = []
		size = len(arr)
		for i in range(size):
			if arr[i] in dict:
				dict[arr[i]] = dict[arr[i]] + 1
			else:
				dict[arr[i]] = 1
		for i in range(size):
			if dict[arr[i]] > 1:
				continue
			else:
				KthIndex = KthIndex - 1
			if KthIndex == 0:
				return arr[i]
		return -1