Given an unsorted array Arr of size N that may contain duplicates. Also given a number K which is smaller than size of array. Find if array contains duplicates within K distance.
Example 1:
Input: 
K = 3, N = 8
Arr[] = {1, 2, 3, 4, 1, 2, 3, 4}
Output: False
Explanation: 
All duplicates are more than k distance
away.
Example 2:
Input: 
K = 3, N = 6
Arr[] = {1, 2, 3, 1, 4, 5}
Output: True
Explanation: 1 is repeated at distance 3.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function checkDuplicatesWithinKÃ¢â¬â¹() which takes the array of integers arr[], n and k as parameters and returns boolean denoting the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ K ≤ N
1 ≤ Arr[i] ≤ 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3
class Solution:

	def checkDuplicatesWithinK(self,arr, n, k):
		# code here


Solutions:
class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		d = {}
		for i in range(n):
			if arr[i] in d:
				if abs(d[arr[i]] - i) <= k:
					return True
				d[arr[i]] = max(i, d[arr[i]])
			else:
				d[arr[i]] = i
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		d = {}
		for index in range(n):
			elem = arr[index]
			start = 0 if index < k else index - k
			end = k if index < k else start + k
			if elem in d and elem in arr[start:end]:
				return True
			else:
				d[elem] = index
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		setti = set()
		for i in range(k + 1):
			if arr[i] in setti:
				return True
			setti.add(arr[i])
		for i in range(k + 1, n):
			setti.remove(arr[i - k - 1])
			if arr[i] in setti:
				return True
			setti.add(arr[i])
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		window = dict()
		for i in range(0, n):
			if i - (k + 1) >= 0:
				del window[arr[i - (k + 1)]]
			if arr[i] in window.keys():
				return True
			window[arr[i]] = True
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		freq = {}
		for i in range(k):
			if arr[i] in freq:
				return True
			else:
				freq[arr[i]] = 1
		for i in range(k, n):
			if freq[arr[i - k]] == 1:
				del freq[arr[i - k]]
			else:
				freq[arr[i - k]] -= 1
			if arr[i] in freq:
				return True
			else:
				freq[arr[i]] = 1
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		for i in range(n):
			if len(arr[i:i + k]) != len(set(arr[i:i + k])):
				return True
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = i
			elif i - d[arr[i]] <= k:
				return True
			else:
				d[arr[i]] = i
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		s = set()
		d = k + 1
		for i in range(d):
			s.add(arr[i])
		if len(s) != d:
			return True
		for i in range(d, n):
			s.remove(arr[i - d])
			s.add(arr[i])
			if len(s) != d:
				return True
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		from collections import defaultdict
		d = defaultdict(int)
		for i in range(k + 1):
			d[arr[i]] += 1
		if len(d.keys()) < k + 1:
			return True
		for i in range(k + 1, n):
			d[arr[i]] += 1
			d[arr[i - k - 1]] -= 1
			if d[arr[i - k - 1]] == 0:
				del d[arr[i - k - 1]]
			if len(d.keys()) < k + 1:
				return True
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		d = {}
		n = len(arr)
		for i in range(n):
			if arr[i] in d:
				return True
			else:
				d[arr[i]] = 1
			if i >= k:
				d.pop(arr[i - k])
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		ds1 = {}
		ds2 = {}
		prevDs = {}
		for i in range(n):
			ds1[arr[i]] = ds1.get(arr[i], 0) + 1
			ds2[arr[i]] = i - prevDs.get(arr[i], 0)
			prevDs[arr[i]] = i
		for i in ds1.keys():
			if ds1.get(i, 0) > 1 and ds2[i] <= k:
				return True
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		m = {}
		for i in range(n):
			if arr[i] in m:
				if i - m[arr[i]] < k:
					return True
			m[arr[i]] = i
		return False


class Solution:

	def isdup(self, lst):
		lst.sort()
		for i in range(1, len(lst)):
			if lst[i] == lst[i - 1]:
				return True
		return False

	def checkDuplicatesWithinK(self, arr, n, k):
		for i in range(n):
			if i + k < n:
				if self.isdup(arr[i:i + k + 1]):
					return True
			else:
				return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		for i in range(n):
			r = k
			j = i + 1
			while r > 0 and j < n:
				if arr[i] == arr[j]:
					return True
				j += 1
				r -= 1
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		window = dict()
		for i in range(0, n):
			if i - (k + 1) >= 0:
				del window[arr[i - (k + 1)]]
			if arr[i] in window.keys():
				return True
			window[arr[i]] = True
		return False
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(k, n) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.checkDuplicatesWithinK(arr, n, k)
		print(ans)
		tc -= 1


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		S = []
		for i in range(n):
			if arr[i] in S:
				return 'True'
			S.append(arr[i])
			if i >= k:
				S.remove(arr[i - k])
		return 'False'
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(k, n) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.checkDuplicatesWithinK(arr, n, k)
		print(ans)
		tc -= 1


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		has = []
		for i in range(n):
			if arr[i] in has:
				return True
			has.append(arr[i])
			if i >= k:
				has.remove(arr[i - k])
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		hm = {}
		for (i, x) in enumerate(arr):
			if x in hm and i - hm[x] <= k:
				return True
			hm[x] = i
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		k -= 1
		d = dict()
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		while len(arr) != 0:
			a = arr[0]
			arr.pop(0)
			d[a] -= 1
			if d[a] > 0 and arr.index(a) <= k:
				return True
		return False


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		hashMap = {}
		answer = False
		for numberIndex in range(0, n):
			if not arr[numberIndex] in hashMap:
				hashMap[arr[numberIndex]] = [numberIndex, numberIndex, 0]
			else:
				hashMap[arr[numberIndex]][0] = hashMap[arr[numberIndex]][1]
				hashMap[arr[numberIndex]][1] = numberIndex
				distance = hashMap[arr[numberIndex]][1] - hashMap[arr[numberIndex]][0]
				if distance <= k:
					hashMap[arr[numberIndex]][2] = distance
		for number in hashMap:
			if hashMap[number][2] != 0:
				answer = True
				break
		return answer


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		hashMap = {}
		answer = False
		for i in range(0, n):
			if not arr[i] in hashMap:
				hashMap[arr[i]] = [i, i, 0]
			else:
				hashMap[arr[i]][0] = hashMap[arr[i]][1]
				hashMap[arr[i]][1] = i
				if hashMap[arr[i]][1] - hashMap[arr[i]][0] <= k:
					hashMap[arr[i]][2] = hashMap[arr[i]][1] - hashMap[arr[i]][0]
		for num in hashMap:
			if hashMap[num][2] != 0:
				answer = True
				break
		return answer


class Solution:

	def checkDuplicatesWithinK(self, arr, n, k):
		hashMap = {}
		for i in range(0, n):
			if arr[i] in hashMap:
				if i - hashMap[arr[i]] < k:
					return True
			hashMap[arr[i]] = i
		return False


class Solution:

	def checkDuplicatesWithinK(self, a, n, k):
		m = {}
		for i in range(len(a)):
			if a[i] not in m:
				m[a[i]] = i
			else:
				if i - m[a[i]] <= k:
					return True
				m[a[i]] = i
		return False