Given an array of integers and a number K. Find the count of distinct elements in every window of size K in the array.
Example 1:
Input:
N = 7, K = 4
A[] = {1,2,1,3,4,2,3}
Output: 3 4 4 3
Explanation: Window 1 of size k = 4 is
1 2 1 3. Number of distinct elements in
this window are 3. 
Window 2 of size k = 4 is 2 1 3 4. Number
of distinct elements in this window are 4.
Window 3 of size k = 4 is 1 3 4 2. Number
of distinct elements in this window are 4.
Window 4 of size k = 4 is 3 4 2 3. Number
of distinct elements in this window are 3.
Example 2:
Input:
N = 3, K = 2
A[] = {4,1,1}
Output: 2 1
Your Task:
Your task is to complete the function countDistinct() which takes the array A[], the size of the array(N) and the window size(K) as inputs and returns an array containing the count of distinct elements in every contiguous window of size K in the array A[].
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= K <= N <= 10^{5}
1 <= A[i] <= 10^{5 }, for each valid i

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Amortized analysis

Starter code: 
class Solution:
    def countDistinct(self, A, N, K):
        # Code here

Solutions:
class Solution:

	def countDistinct(self, A, N, K):
		ans = []
		h = {}
		for i in range(K):
			if A[i] in h:
				h[A[i]] += 1
			else:
				h[A[i]] = 1
		ans.append(len(h))
		for j in range(1, N - K + 1):
			if h[A[j - 1]] > 1:
				h[A[j - 1]] -= 1
			else:
				del h[A[j - 1]]
			if A[j + K - 1] in h:
				h[A[j + K - 1]] += 1
			else:
				h[A[j + K - 1]] = 1
			ans.append(len(h))
		return ans


from collections import defaultdict

class Solution:

	def countDistinct(self, A, N, K):
		if N < K:
			return []
		if N == 1:
			return [len(A)]
		ans = []
		mp = defaultdict(lambda : 0)
		dist_count = 0
		for i in range(K):
			if mp[A[i]] == 0:
				dist_count += 1
			mp[A[i]] += 1
		ans.append(dist_count)
		for i in range(K, n):
			if mp[A[i - K]] == 1:
				dist_count -= 1
			mp[A[i - K]] -= 1
			if mp[A[i]] == 0:
				dist_count += 1
			mp[A[i]] += 1
			ans.append(dist_count)
		return ans


class Solution:

	def countDistinct(self, A, N, K):
		mp = dict()
		res = []
		(start, end) = (0, 0)
		while end <= len(A) - 1:
			val = A[end]
			if val not in mp:
				mp[val] = 0
			mp[val] += 1
			while end - start + 1 > k:
				val = A[start]
				mp[val] -= 1
				if mp[val] == 0:
					mp.pop(val)
				start += 1
			if end - start + 1 == k:
				res.append(len(mp))
			end += 1
		return res


class Solution:

	def countDistinct(self, A, N, K):
		l = []
		d = {}
		c = 0
		p = 0
		for i in A:
			p += 1
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
				c += 1
			if p >= K:
				l.append(c)
				d[arr[p - K]] -= 1
				if d[arr[p - K]] == 0:
					d.pop(arr[p - k])
					c -= 1
		return l


class Solution:

	def countDistinct(self, A, N, K):
		dic = {}
		c = 0
		a = []
		start = 0
		for i in range(K):
			if A[i] not in dic:
				dic[A[i]] = 1
				c += 1
			else:
				dic[A[i]] += 1
		a.append(c)
		for i in range(K, N):
			dic[A[start]] -= 1
			if dic[A[start]] == 0:
				dic.pop(A[start])
				c -= 1
			start += 1
			if A[i] in dic:
				dic[A[i]] += 1
			else:
				dic[A[i]] = 1
				c += 1
			a.append(c)
		return a


class Solution:

	def countDistinct(self, A, N, K):
		result = []
		freq = {}
		for i in range(K):
			if A[i] in freq:
				freq[A[i]] += 1
			else:
				freq[A[i]] = 1
		result.append(len(freq.keys()))
		start = 1
		end = start + K - 1
		while end < N:
			freq[A[start - 1]] -= 1
			if freq[A[start - 1]] == 0:
				del freq[A[start - 1]]
			if A[end] in freq:
				freq[A[end]] += 1
			else:
				freq[A[end]] = 1
			result.append(len(freq.keys()))
			start += 1
			end += 1
		return result


class Solution:

	def countDistinct(self, A, N, K):
		i = 0
		j = 0
		res = []
		hmap = {}
		left = 0
		for i in range(K):
			hmap[arr[i]] = hmap.get(arr[i], 0) + 1
		res.append(len(hmap))
		for right in range(k, n):
			hmap[arr[left]] -= 1
			if hmap[arr[left]] == 0:
				del hmap[arr[left]]
			left += 1
			hmap[arr[right]] = hmap.get(arr[right], 0) + 1
			res.append(len(hmap))
		return res


from collections import defaultdict

class Solution:

	def countDistinct(self, A, N, K):
		mp = defaultdict(lambda : 0)
		lis = []
		dist_count = 0
		for i in range(K):
			if mp[arr[i]] == 0:
				dist_count += 1
			mp[arr[i]] += 1
		lis.append(dist_count)
		for i in range(K, N):
			if mp[arr[i - K]] == 1:
				dist_count -= 1
			mp[arr[i - K]] -= 1
			if mp[arr[i]] == 0:
				dist_count += 1
			mp[arr[i]] += 1
			lis.append(dist_count)
		return lis


class Solution:

	def countDistinct(self, lst, n, k):
		from collections import deque
		i = 0
		j = 0
		d = {}
		ans = []
		while j < len(lst):
			d[lst[j]] = 1 + d.get(lst[j], 0)
			if j - i + 1 < k:
				j = j + 1
			elif j - i + 1 == k:
				ans.append(len(d.keys()))
				d[lst[i]] = d[lst[i]] - 1
				if d[lst[i]] == 0:
					d.pop(lst[i])
				i = i + 1
				j = j + 1
		return ans


class Solution:

	def countDistinct(self, arr, n, k):
		result = []
		hmap = {}
		for i in range(k):
			if arr[i] in hmap:
				hmap[arr[i]] += 1
			else:
				hmap[arr[i]] = 1
		result.append(len(hmap))
		for i in range(k, n):
			if hmap[arr[i - k]] == 1:
				del hmap[arr[i - k]]
			else:
				hmap[arr[i - k]] -= 1
			if arr[i] in hmap:
				hmap[arr[i]] += 1
			else:
				hmap[arr[i]] = 1
			result.append(len(hmap))
		return result


class Solution:

	def countDistinct(self, A, N, K):
		ans = []
		d = {}
		for i in range(K):
			if A[i] in d:
				d[A[i]] += 1
			else:
				d[A[i]] = 1
		ans.append(len(d))
		for i in range(K, N):
			if d[A[i - K]] == 1:
				del d[A[i - K]]
			else:
				d[A[i - K]] -= 1
			if A[i] not in d:
				d[A[i]] = 1
			else:
				d[A[i]] += 1
			ans.append(len(d))
		return ans


from collections import defaultdict

class Solution:

	def countDistinct(self, nums, n, k):
		freq = defaultdict(int)
		result = []
		cnt = 0
		rem = 0
		for i in range(n):
			if i < k:
				if freq[nums[i]] == 0:
					cnt += 1
				freq[nums[i]] += 1
			else:
				result.append(cnt)
				freq[nums[rem]] -= 1
				if freq[nums[rem]] == 0:
					cnt -= 1
				rem += 1
				freq[nums[i]] += 1
				if freq[nums[i]] == 1:
					cnt += 1
		result.append(cnt)
		return result


class Solution:

	def countDistinct(self, A, N, K):
		ans = []
		d = {}
		i = 0
		j = 0
		while j < N:
			if A[j] in d:
				d[A[j]] += 1
			else:
				d[A[j]] = 1
			if j - i + 1 == K:
				ans.append(len(d))
				d[A[i]] -= 1
				if d[A[i]] == 0:
					d.pop(A[i])
				i += 1
				j += 1
			elif j - i + 1 < K:
				j += 1
		return ans


from collections import defaultdict

class Solution:

	def countDistinct(self, A, N, K):
		distinct_counts = []
		freq = defaultdict(int)
		distinct_count = 0
		for i in range(K):
			if freq[A[i]] == 0:
				distinct_count += 1
			freq[A[i]] += 1
		distinct_counts.append(distinct_count)
		for i in range(K, N):
			freq[A[i - K]] -= 1
			if freq[A[i - K]] == 0:
				distinct_count -= 1
			if freq[A[i]] == 0:
				distinct_count += 1
			freq[A[i]] += 1
			distinct_counts.append(distinct_count)
		return distinct_counts


class Solution:

	def countDistinct(self, A, N, K):
		arr = []
		dict = {}
		for i in range(k):
			if A[i] in dict:
				dict[A[i]] += 1
			else:
				dict[A[i]] = 1
		arr.append(len(dict))
		for i in range(k, N):
			c = A[i]
			if c in dict:
				dict[c] += 1
			else:
				dict[c] = 1
			dict[A[i - k]] -= 1
			if dict[A[i - k]] == 0:
				del dict[A[i - k]]
			arr.append(len(dict))
		return arr


from collections import deque

class Solution:

	def countDistinct(self, A, N, K):
		res = []
		d = {}
		for i in range(k):
			d[A[i]] = d.get(A[i], 0) + 1
		start = 0
		for i in range(K, len(A)):
			res.append(len(d))
			d[A[start]] -= 1
			if d[A[start]] <= 0:
				del d[A[start]]
			d[A[i]] = d.get(A[i], 0) + 1
			start += 1
		res.append(len(d))
		return res


class Solution:

	def countDistinct(self, A, N, K):
		dict = {}
		start = 0
		end = 0
		ans = []
		counter = 0
		while start < N - K + 1 and end < N:
			if A[end] not in dict:
				dict[A[end]] = 1
			else:
				dict[A[end]] += 1
			if end - start == K - 1:
				ans.append(len(dict))
				dict[A[start]] -= 1
				d = dict[A[start]]
				if d == 0:
					del dict[A[start]]
				start += 1
			end += 1
		return ans


class Solution:

	def countDistinct(self, A, N, K):
		d = {}
		li = []
		l = 0
		for i in range(0, K):
			if A[i] in d.keys():
				d[A[i]] += 1
			else:
				d[A[i]] = 1
		li.append(len(d.keys()))
		for i in range(K, N):
			d[A[l]] -= 1
			if A[i] not in d.keys():
				d[A[i]] = 1
			else:
				d[A[i]] += 1
			if d[A[l]] == 0:
				d.pop(A[l])
			l += 1
			li.append(len(d.keys()))
		return li


import collections

class Solution:

	def countDistinct(self, A, N, K):
		freq_each = collections.defaultdict(int)
		sol = [0] * (N - K + 1)
		l = 1
		r = j = 0
		while r < K:
			freq_each[A[r]] += 1
			r += 1
		sol[j] = len(freq_each)
		j += 1
		while r < N:
			freq_each[A[r]] += 1
			freq_each[A[l - 1]] -= 1
			if freq_each[A[l - 1]] == 0:
				del freq_each[A[l - 1]]
			sol[j] = len(freq_each)
			j += 1
			r += 1
			l += 1
		return sol


from collections import defaultdict

class Solution:

	def countDistinct(self, A, N, K):
		dic = defaultdict()
		i = 0
		j = 0
		res = []
		while j < N:
			if A[j] in dic:
				dic[A[j]] += 1
			else:
				dic[A[j]] = 1
			if j - i + 1 < K:
				j += 1
			elif j - i + 1 == K:
				res.append(len(dic))
				dic[A[i]] -= 1
				if dic[A[i]] == 0:
					del dic[A[i]]
				i += 1
				j += 1
		return res


class Solution:

	def countDistinct(self, A, N, K):
		ans = []
		mpp = dict()
		(j, i) = (0, 0)
		while j < N:
			if A[j] in mpp:
				mpp[A[j]] = mpp[A[j]] + 1
			else:
				mpp[A[j]] = 1
			if j - i + 1 == k:
				ans.append(len(mpp))
				mpp[A[i]] = mpp[A[i]] - 1
				if mpp[A[i]] == 0:
					mpp.pop(A[i])
				i += 1
			j += 1
		return ans


from collections import defaultdict

class Solution:

	def countDistinct(self, A, N, K):
		mp = defaultdict(lambda : 0)
		l = []
		count = 0
		for i in range(0, K):
			if mp[A[i]] == 0:
				count += 1
			mp[A[i]] += 1
		l.append(count)
		for i in range(K, N):
			if mp[A[i - K]] == 1:
				count -= 1
			mp[A[i - K]] -= 1
			if mp[A[i]] == 0:
				count += 1
			mp[A[i]] += 1
			l.append(count)
		return l


class Solution:

	def countDistinct(self, A, N, K):
		mp = {}
		for i in range(K):
			if A[i] not in mp.keys():
				mp[A[i]] = 1
			else:
				mp[A[i]] += 1
		countDis_arr = [len(mp)]
		for j in range(K, N):
			mp[A[j - K]] -= 1
			if mp[A[j - K]] == 0:
				del mp[A[j - K]]
			if A[j] not in mp.keys():
				mp[A[j]] = 1
			else:
				mp[A[j]] += 1
			countDis_arr.append(len(mp))
		return countDis_arr


from collections import defaultdict

class Solution:

	def countDistinct(self, A, n, k):
		mp = defaultdict(lambda : 0)
		dist_count = 0
		for i in range(k):
			if mp[A[i]] == 0:
				dist_count += 1
			mp[A[i]] += 1
		res = []
		res.append(dist_count)
		for i in range(k, n):
			if mp[A[i - k]] == 1:
				dist_count -= 1
			mp[A[i - k]] -= 1
			if mp[A[i]] == 0:
				dist_count += 1
			mp[A[i]] += 1
			res.append(dist_count)
		return res


class Solution:

	def countDistinct(self, A, N, K):
		d = {}
		for i in range(K):
			if A[i] in d:
				d[A[i]] = d[A[i]] + 1
			else:
				d[A[i]] = 1
		res = [len(d)]
		for i in range(K, N):
			d[A[i - K]] = d[A[i - K]] - 1
			if d[A[i - K]] == 0:
				d.pop(A[i - K])
			if A[i] in d:
				d[A[i]] = d[A[i]] + 1
			else:
				d[A[i]] = 1
			res.append(len(d))
		return res


class Solution:

	def countDistinct(self, A, N, K):
		hashmap = {}
		res = []
		for i in range(K):
			if A[i] in hashmap:
				hashmap[A[i]] += 1
			else:
				hashmap[A[i]] = 1
		res.append(len(hashmap))
		start = 1
		end = K
		while end < N:
			hashmap[A[start - 1]] -= 1
			if A[end] in hashmap:
				hashmap[A[end]] += 1
			else:
				hashmap[A[end]] = 1
			if hashmap[A[start - 1]] == 0:
				del hashmap[A[start - 1]]
			res.append(len(hashmap))
			start += 1
			end += 1
		return res


class Solution:

	def countDistinct(self, A, N, K):
		mp = {}
		res = []
		for i in range(K):
			mp[A[i]] = mp.get(A[i], 0) + 1
		res.append(len(mp))
		for i in range(K, N):
			mp[A[i - K]] = mp[A[i - k]] - 1
			if mp[A[i - K]] <= 0:
				mp.pop(A[i - K])
			mp[A[i]] = mp.get(A[i], 0) + 1
			res.append(len(mp))
		return res


class Solution:

	def countDistinct(self, A, N, K):
		hash = {}
		for i in range(min(K, N)):
			hash[A[i]] = hash.get(A[i], 0) + 1
		res = [len(hash)]
		i = 0
		for j in range(K, N):
			hash[A[i]] -= 1
			if hash[A[i]] == 0:
				del hash[A[i]]
			hash[A[j]] = hash.get(A[j], 0) + 1
			res.append(len(hash))
			i += 1
		return res


class Solution:

	def countDistinct(self, A, N, K):
		window = K
		slides = N - K + 1
		first = A[0:K]
		Output = [len(set(first))]
		d = {}
		for i in first:
			d[i] = d.get(i, 0) + 1
		for i in range(1, slides):
			Add = A[window]
			Remove = A[i - 1]
			d[Add] = d.get(Add, 0) + 1
			d[Remove] = d.get(Remove) - 1
			if d.get(Remove) == 0:
				d.pop(Remove)
			Output.append(len(d))
			window += 1
		return Output


class Solution:

	def countDistinct(self, A, N, K):
		ans = []
		s = {}
		cnt = 0
		for i in range(K):
			s[A[i]] = s.get(A[i], 0) + 1
		cnt = len(s)
		ans.append(cnt)
		j = 0
		for i in range(K, N):
			s[A[i]] = s.get(A[i], 0) + 1
			if s[A[i]] == 1:
				cnt += 1
			s[A[j]] -= 1
			if s[A[j]] == 0:
				cnt -= 1
			j += 1
			ans.append(cnt)
		return ans


class Solution:

	def countDistinct(self, A, N, K):
		l = []
		d = {}
		for i in range(0, k):
			if A[i] in d:
				d[A[i]] += 1
			else:
				d[A[i]] = 1
		l.append(len(d))
		for j in range(1, N - K + 1):
			if A[j + K - 1] in d:
				d[A[j + K - 1]] += 1
			else:
				d[A[j + K - 1]] = 1
			d[A[j - 1]] -= 1
			if d[A[j - 1]] == 0:
				del d[A[j - 1]]
			l.append(len(d))
		return l


class Solution:

	def countDistinct(self, A, N, K):
		dic = {}
		for i in range(K):
			if A[i] in dic:
				dic[A[i]] += 1
			else:
				dic[A[i]] = 1
		l = 0
		b = []
		b.append(len(dic))
		for r in range(K, N):
			dic[A[l]] -= 1
			if dic[A[l]] == 0:
				del dic[A[l]]
			l += 1
			if A[r] in dic:
				dic[A[r]] += 1
			else:
				dic[A[r]] = 1
			b.append(len(dic))
		return b


from collections import defaultdict

class Solution:

	def countDistinct(self, A, N, K):
		ans = []
		dd = defaultdict()
		for i in range(K):
			if A[i] in dd:
				dd[A[i]] += 1
			else:
				dd[A[i]] = 1
		ans.append(len(dd))
		for i in range(K, N):
			if dd[A[i - K]] == 1:
				del dd[A[i - K]]
			else:
				dd[A[i - K]] -= 1
			if A[i] in dd:
				dd[A[i]] += 1
			else:
				dd[A[i]] = 1
			ans.append(len(dd))
		return ans


class Solution:

	def countDistinct(self, A, N, K):
		l = []
		d = {}
		count = 0
		for i in range(K):
			if A[i] not in d:
				d[A[i]] = 1
				count += 1
			else:
				d[A[i]] += 1
		l.append(count)
		if d[A[0]] == 1:
			del d[A[0]]
			count -= 1
		else:
			d[A[0]] -= 1
		st = 1
		i += 1
		while i < len(A):
			if A[i] not in d:
				d[A[i]] = 1
				count += 1
			else:
				d[A[i]] += 1
			l.append(count)
			i += 1
			if d[A[st]] == 1:
				count -= 1
				del d[A[st]]
			else:
				d[A[st]] -= 1
			st += 1
		return l


class Solution:

	def countDistinct(self, A, N, K):
		d = {}
		ans = []
		for i in range(K - 1):
			if A[i] in d:
				d[A[i]] += 1
			else:
				d[A[i]] = 1
		i = K - 1
		j = 0
		while i < N:
			if A[i] in d:
				d[A[i]] += 1
			else:
				d[A[i]] = 1
			ans.append(len(d))
			if d[A[j]] == 1:
				del d[A[j]]
			else:
				d[A[j]] -= 1
			i += 1
			j += 1
		return ans


class Solution:

	def countDistinct(self, A, N, K):
		map = {}
		B = []
		for i in range(K):
			if A[i] not in map:
				map[A[i]] = 1
			else:
				map[A[i]] += 1
		B.append(len(map))
		for j in range(1, N - K + 1):
			if A[j + K - 1] not in map:
				map[A[j + K - 1]] = 1
			else:
				map[A[j + K - 1]] += 1
			map[A[j - 1]] -= 1
			if map[A[j - 1]] == 0:
				del map[A[j - 1]]
			B.append(len(map))
		return B


class Solution:

	def countDistinct(self, A, N, K):
		res = []
		hash = {}
		i = 0
		while i < K:
			if A[i] in hash:
				hash[A[i]] += 1
			else:
				hash[A[i]] = 1
			i += 1
		res = [len(hash)]
		j = 0
		while i < N:
			hash[A[j]] -= 1
			if hash[A[j]] == 0:
				del hash[A[j]]
			if A[i] in hash:
				hash[A[i]] += 1
			else:
				hash[A[i]] = 1
			res.append(len(hash))
			i += 1
			j += 1
		return res


class Solution:

	def countDistinct(self, A, N, K):
		dic = {}
		lst = []
		cnt = 0
		for i in range(N):
			cnt += 1
			if A[i] not in dic:
				dic[A[i]] = 1
			else:
				dic[A[i]] += 1
			if cnt >= k:
				lst.append(len(dic))
				dic[A[i + 1 - k]] -= 1
				if dic[A[i + 1 - k]] == 0:
					dic.pop(A[i + 1 - k])
		return lst


from collections import defaultdict

class Solution:

	def countDistinct(self, A, N, K):
		l = defaultdict(int)
		t = []
		i = 0
		for j in range(N):
			if j + 1 > k:
				t.append(len(l))
				if l[A[i]] > 1:
					l[A[i]] -= 1
				else:
					del l[A[i]]
				i += 1
			l[A[j]] += 1
		t.append(len(l))
		return t


class Solution:

	def countDistinct(self, A, N, K):
		arr = []
		l = r = 0
		mp = {}
		while r < N:
			mp[A[r]] = mp.get(A[r], 0) + 1
			if r - l + 1 == k:
				arr.append(len(mp))
				mp[A[l]] = mp[A[l]] - 1
				if mp[A[l]] == 0:
					del mp[A[l]]
				l += 1
			r += 1
		return arr


class Solution:

	def countDistinct(self, A, N, K):
		f = {}
		res = []
		for i in range(K):
			if A[i] in f:
				f[A[i]] += 1
			else:
				f[A[i]] = 1
		res.append(len(f))
		for j in range(K, N):
			f[A[j - K]] -= 1
			if f[A[j - K]] == 0:
				f.pop(A[j - K])
			else:
				pass
			if A[j] in f:
				f[A[j]] += 1
			else:
				f[A[j]] = 1
			res.append(len(f))
		return res


from collections import Counter

class Solution:

	def countDistinct(self, A, N, K):
		res = []
		mp = Counter(arr[0:k])
		res.append(len(mp))
		for i in range(k, len(A)):
			x = A[i - K]
			mp[x] -= 1
			mp[A[i]] += 1
			if mp[x] == 0:
				del mp[x]
			res.append(len(mp))
		return res


class Solution:

	def countDistinct(self, A, N, K):
		a = {}
		ans = []
		for i in range(K):
			if A[i] not in a:
				a[A[i]] = 1
			else:
				a[A[i]] += 1
		ans.append(len(a))
		for j in range(1, N - K + 1):
			if A[j + K - 1] not in a:
				a[A[j + K - 1]] = 1
			else:
				a[A[j + K - 1]] += 1
			a[A[j - 1]] -= 1
			if a[A[j - 1]] == 0:
				del a[A[j - 1]]
			ans.append(len(a))
		return ans


from collections import defaultdict

class Solution:

	def countDistinct(self, arr, n, k):
		count = defaultdict(int)
		res = []
		for i in range(k):
			count[arr[i]] += 1
		res.append(len(count))
		start = 0
		end = k
		while end < n:
			count[arr[end]] += 1
			if count[arr[start]] > 1:
				count[arr[start]] -= 1
			else:
				del count[arr[start]]
			start += 1
			res.append(len(count))
			end += 1
		return res


from collections import defaultdict as dd

class Solution:

	def countDistinct(self, A, N, K):
		d = dd(int)
		i = 0
		tmp = i
		end = tmp + K - 1
		uni = 0
		arr = []
		while i < N:
			d[A[i]] += 1
			if d[A[i]] == 1:
				uni += 1
			if end == i:
				d[A[tmp]] -= 1
				arr.append(uni)
				if d[A[tmp]] == 0:
					uni -= 1
				tmp += 1
				end += 1
			i += 1
		return arr


class Solution:

	def countDistinct(self, a, n, k):
		map = {}
		res = []
		for i in range(k):
			map[a[i]] = map.get(a[i], 0) + 1
		res.append(len(map))
		for i in range(k, n):
			if map[a[i - k]] == 1:
				del map[a[i - k]]
			else:
				map[a[i - k]] = map.get(a[i - k]) - 1
			map[a[i]] = map.get(a[i], 0) + 1
			res.append(len(map))
		return res


class Solution:

	def countDistinct(self, a, n, k):
		lis = []
		dic = dict()
		for i in range(k):
			if a[i] in dic:
				dic[a[i]] += 1
			else:
				dic[a[i]] = 1
		lis.append(len(dic))
		for j in range(k, n):
			dic[a[j - k]] -= 1
			if dic[a[j - k]] == 0:
				del dic[a[j - k]]
			if a[j] in dic:
				dic[a[j]] += 1
			else:
				dic[a[j]] = 1
			lis.append(len(dic))
		return lis


class Solution:

	def countDistinct(self, A, N, K):
		ans = []
		d = {}
		prev = 0
		for i in range(K):
			if A[i] in d:
				d[A[i]] = d[A[i]] + 1
			else:
				d[A[i]] = 1
				prev = prev + 1
		ans.append(prev)
		for i in range(N - K):
			d[A[i]] = d[A[i]] - 1
			if d[A[i]] == 0:
				prev = prev - 1
			if A[i + K] in d:
				if d[A[i + k]] == 0:
					prev = prev + 1
					d[A[i + k]] += 1
				elif d[A[i + k]] > 0:
					d[A[i + k]] += 1
			else:
				d[A[i + k]] = 1
				prev = prev + 1
			ans.append(prev)
		return ans
		return ans


class Solution:

	def countDistinct(self, a, n, k):
		times = {}
		result = []
		for i in range(k):
			if a[i] not in times:
				times[a[i]] = 1
			else:
				times[a[i]] += 1
		for i in range(1, n - k + 1):
			result.append(len(times))
			times[a[i - 1]] -= 1
			if times[a[i - 1]] == 0:
				times.pop(a[i - 1])
			val = a[i + k - 1]
			if val not in times:
				times[val] = 1
			else:
				times[val] += 1
		result.append(len(times))
		return result


class Solution:

	def addElementIntoDict(ele, countDict):
		if ele in countDict:
			countDict[ele] += 1
		else:
			countDict[ele] = 1

	def countDistinct(self, A, N, K):
		if K > N:
			return -1
		outputList = []
		outputSet = set()
		outputDict = {}
		for i in range(0, K):
			Solution.addElementIntoDict(A[i], outputDict)
		outputList.append(len(outputDict))
		for j in range(K, N):
			if A[j - K] in outputDict:
				outputDict[A[j - K]] -= 1
				if outputDict[A[j - K]] == 0:
					outputDict.pop(A[j - K])
			Solution.addElementIntoDict(A[j], outputDict)
			outputList.append(len(outputDict))
		return outputList


class Solution:

	def countDistinct(self, A, N, K):
		dic = dict()
		i = 0
		j = 0
		res = []
		while j < N:
			if A[j] in dic:
				dic[A[j]] += 1
			else:
				dic[A[j]] = 1
			if j - i + 1 < K:
				j += 1
			elif j - i + 1 == K:
				res.append(len(dic))
				dic[A[i]] -= 1
				if dic[A[i]] == 0:
					del dic[A[i]]
				i += 1
				j += 1
		return res


class Solution:

	def countDistinct(self, A, N, K):
		dicti = {}
		lst = []
		for i in range(K):
			if A[i] not in dicti:
				dicti[A[i]] = 1
			else:
				dicti[A[i]] += 1
		lst.append(len(dicti))
		for i in range(K, N):
			if dicti[A[i - K]] == 1:
				del dicti[A[i - K]]
			else:
				dicti[A[i - K]] -= 1
			if A[i] in dicti:
				dicti[A[i]] += 1
			else:
				dicti[A[i]] = 1
			lst.append(len(dicti))
		return lst


class Solution:

	def countDistinct(self, A, N, K):
		ans = []
		m = {}
		for i in range(0, K):
			if A[i] in m:
				m[A[i]] += 1
			else:
				m[A[i]] = 1
		ans.append(len(m.keys()))
		for i in range(K, N):
			if A[i - K] in m:
				m[A[i - K]] -= 1
			if m[A[i - K]] == 0:
				del m[A[i - K]]
			if A[i] in m:
				m[A[i]] += 1
			else:
				m[A[i]] = 1
			ans.append(len(m.keys()))
		return ans


class Solution:

	def countDistinct(self, A, N, K):
		p1 = 0
		p2 = k
		d = {}
		c = 0
		for i in range(k):
			if A[i] in d:
				d[A[i]] += 1
			else:
				d[A[i]] = 1
				c += 1
		l1 = [c]
		while p2 != N:
			c = 0
			if A[p2] in d:
				d[A[p2]] += 1
			else:
				d[A[p2]] = 1
			d[A[p1]] -= 1
			if d[A[p1]] < 1:
				d.pop(A[p1])
			c = len(d)
			l1.append(c)
			p2 += 1
			p1 += 1
		return l1


class Solution:

	def countDistinct(self, a, N, k):
		dic = {}
		ans = []
		for i in range(k):
			dic[a[i]] = dic.get(a[i], 0) + 1
		ans.append(len(dic))
		st = 0
		for i in range(k, len(a)):
			dic[a[i]] = dic.get(a[i], 0) + 1
			dic[a[st]] -= 1
			if dic[a[st]] == 0:
				del dic[a[st]]
			ans.append(len(dic))
			st += 1
		return ans


class Solution:

	def countDistinct(self, A, N, K):
		d = dict()
		result = []
		count = 0
		i = 0
		for j in range(N):
			d[A[j]] = d.get(A[j], 0) + 1
			if j + 1 - i == K:
				result.append(len(d))
			elif j + 1 - i > K:
				d[A[i]] -= 1
				if d[A[i]] == 0:
					del d[A[i]]
				i += 1
				result.append(len(d))
		return result


class Solution:

	def countDistinct(self, arr, n, k):
		d = {}
		for i in range(k):
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		ans = []
		i = 0
		j = k - 1
		while j < n - 1:
			ans.append(len(d))
			prev_ele = arr[i]
			d[prev_ele] -= 1
			if d[prev_ele] == 0:
				del d[prev_ele]
			i += 1
			j += 1
			if arr[j] in d:
				d[arr[j]] += 1
			else:
				d[arr[j]] = 1
		else:
			ans.append(len(d))
		return ans