Given an integer array arr of size N and an integer k, return the number of good subarrays of arr.
A good array is an array where the number of different integers in that is exactly k.
	For example, {1, 3, 4, 4, 1} has 3 different integers: 1, 3, and 4.
Note : A subarray is a contiguous part of an array.
Example 1:
Input:
N = 5
k = 2
arr[ ] = {1, 2, 1, 2, 3}
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: {1, 2}, {2, 1}, {1, 2}, {2, 3}, {1, 2, 1}, {2, 1, 2}, {1, 2, 1, 2}.
 
Example 2:
Input:
N = 5
k = 3
arr[ ] = {1, 2, 1, 3, 4}
Output: 3
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function subarrayCount() which takes the array of integers arr , an integer N and k as parameters and returns a number of good subarrays.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ k ≤ N
^{1 }≤ arr_{i  }≤ N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    def subarrayCount(self, arr, N, k):

        # Code here

Solutions:
class Solution:

	def subarrayCount(self, arr, N, k):
		count = self.AtMostk(arr, k) - self.AtMostk(arr, k - 1)
		return count

	def AtMostk(self, arr, k):
		count = 0
		i = 0
		j = 0
		a = {}
		while j < len(arr):
			a[arr[j]] = a.get(arr[j], 0) + 1
			while len(a) > k:
				a[arr[i]] -= 1
				if a[arr[i]] == 0:
					del a[arr[i]]
				i += 1
			count += j - i + 1
			j += 1
		return count


class Solution:

	def subarrayCount(self, arr, N, k):

		def helper(k):
			d = {}
			(i, j, ans) = (0, 0, 0)
			while j < N:
				d[arr[j]] = d.get(arr[j], 0) + 1
				if len(d) > k:
					while len(d) > k:
						d[arr[i]] -= 1
						if d[arr[i]] == 0:
							del d[arr[i]]
						i += 1
				ans += j - i + 1
				j += 1
			return ans
		return helper(k) - helper(k - 1)


class Solution:

	def subarrayCount(self, arr, n, k):

		def find(arr, n, k):
			dic = {}
			ans = 0
			j = 0
			for i in range(n):
				if arr[i] in dic:
					dic[arr[i]] += 1
				else:
					dic[arr[i]] = 1
				while len(dic) > k and j <= i:
					dic[arr[j]] -= 1
					if dic[arr[j]] == 0:
						del dic[arr[j]]
					j += 1
				ans += i - j + 1
			return ans
		return find(arr, n, k) - find(arr, n, k - 1)


class Solution:

	def subarrayCount(self, arr, N, k):
		return self.atmost(arr, N, k) - self.atmost(arr, N, k - 1)

	def atmost(self, arr, N, k):
		(i, ans) = (0, 0)
		d = {}
		for j in range(N):
			d[arr[j]] = 1 + d.get(arr[j], 0)
			while len(d) > k:
				d[arr[i]] -= 1
				if d[arr[i]] == 0:
					del d[arr[i]]
				i += 1
			ans += j - i + 1
		return ans


class Solution:

	def subarrayCount(self, arr, N, k):
		return self.atMost(arr, N, k) - self.atMost(arr, N, k - 1)

	def atMost(self, arr, N, k):
		(i, ans) = (0, 0)
		d = {}
		for j in range(N):
			if arr[j] in d:
				d[arr[j]] += 1
			else:
				d[arr[j]] = 1
			while i <= j and len(d) > k:
				d[arr[i]] -= 1
				if d[arr[i]] == 0:
					del d[arr[i]]
				i += 1
			ans += j - i + 1
		return ans


class Solution:

	def atmost(self, arr, k):
		left = 0
		suma = 0
		d = dict()
		for i in range(len(arr)):
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
			while len(d) > k:
				d[arr[left]] -= 1
				if d[arr[left]] == 0:
					del d[arr[left]]
				left += 1
			suma += i - left + 1
		return suma

	def subarrayCount(self, arr, N, k):
		return self.atmost(arr, k) - self.atmost(arr, k - 1)


class Solution:

	def subarrayCount(self, arr, N, k):
		return self.subArrayMax(arr, N, k) - self.subArrayMax(arr, N, k - 1)

	def subArrayMax(self, arr, N, k):
		(i, j, ans) = (0, 0, 0)
		state = {}
		for j in range(N):
			state[arr[j]] = 1 + state.get(arr[j], 0)
			while len(state) > k:
				state[arr[i]] -= 1
				if state[arr[i]] == 0:
					state.pop(arr[i])
				i += 1
			ans += j - i + 1
		return ans


from collections import defaultdict

class Solution:

	def subarrayCount(self, nums, n, k):

		def atmostk(n, k, nums):
			l = 0
			r = 0
			map = defaultdict(int)
			ans = 0
			while r < n:
				map[nums[r]] += 1
				while len(map) > k:
					map[nums[l]] -= 1
					if map[nums[l]] == 0:
						del map[nums[l]]
					l += 1
				ans += r - l + 1
				r += 1
			return ans
		return atmostk(len(nums), k, nums) - atmostk(len(nums), k - 1, nums)


class Solution:

	def subarrayCount(self, nums, N, k):
		ans = 0
		n = len(nums)
		latest = {}
		unique = 0
		prev = 0
		for i in range(n):
			if nums[i] not in latest:
				unique += 1
			latest[nums[i]] = i
			if unique > k:
				while True:
					if latest[nums[prev]] == prev:
						latest.pop(nums[prev])
						prev += 1
						unique -= 1
						break
					else:
						prev += 1
			if unique == k:
				ans += 1
				tmp = prev
				while True:
					if latest[nums[tmp]] != tmp:
						ans += 1
						tmp += 1
					else:
						break
		return ans


class Solution:

	def solve(self, arr, N, k):
		(count, i) = (0, 0)
		d = {}
		for j in range(N):
			d[arr[j]] = 1 + d.get(arr[j], 0)
			while i <= j and len(d) > k:
				d[arr[i]] = -1 + d.get(arr[i], 0)
				if not d[arr[i]]:
					del d[arr[i]]
				i += 1
			count += j - i + 1
		return count

	def subarrayCount(self, arr, N, k):
		return self.solve(arr, N, k) - self.solve(arr, N, k - 1)


class Solution:

	def subarraysWithDistinct(self, arr, N, k):
		mp = {}
		ans = 0
		startWindow = 0
		for endWindow in range(N):
			if arr[endWindow] in mp:
				mp[arr[endWindow]] += 1
			else:
				mp[arr[endWindow]] = 1
			while len(mp) > k:
				mp[arr[startWindow]] -= 1
				if mp[arr[startWindow]] == 0:
					mp.pop(arr[startWindow])
				startWindow += 1
			ans += endWindow + 1 - startWindow
		return ans

	def subarrayCount(self, arr, N, k):
		return self.subarraysWithDistinct(arr, N, k) - self.subarraysWithDistinct(arr, N, k - 1)


from collections import defaultdict

class Solution:

	def subarrayCount(self, arr, N, k):
		return self.helper(arr, k) - self.helper(arr, k - 1)

	def helper(self, arr, k):
		left = 0
		ans = 0
		hmap = defaultdict(int)
		for right in range(0, len(arr)):
			if arr[right] not in hmap:
				hmap[arr[right]] = 1
			else:
				hmap[arr[right]] += 1
			while len(hmap) > k:
				hmap[arr[left]] -= 1
				if hmap[arr[left]] == 0:
					del hmap[arr[left]]
				left += 1
			ans += right - left + 1
		return ans


class Solution:

	def subarrayCount(self, arr, N, k):
		return self.atMost(arr, N, k) - self.atMost(arr, N, k - 1)

	def atMost(self, arr, n, k):
		i = 0
		j = 0
		count = 0
		map = {}
		while j < n:
			map[arr[j]] = map.get(arr[j], 0) + 1
			while len(map) > k:
				map[arr[i]] -= 1
				if map[arr[i]] == 0:
					del map[arr[i]]
				i += 1
			count += j - i + 1
			j += 1
		return count


class Solution:

	def helper(self, arr, N, k):
		d = {}
		j = 0
		i = 0
		count = 0
		un = 0
		while j < N:
			if arr[j] in d:
				d[arr[j]] = d[arr[j]] + 1
			else:
				d[arr[j]] = 1
				un = un + 1
			while un > k:
				d[arr[i]] = d[arr[i]] - 1
				if d[arr[i]] == 0:
					del d[arr[i]]
					un = un - 1
				i = i + 1
			count = count + (j - i + 1)
			j = j + 1
		return count

	def subarrayCount(self, arr, N, k):
		ans1 = self.helper(arr, N, k)
		ans2 = self.helper(arr, N, k - 1)
		return ans1 - ans2


class Solution:

	def solve(self, arr, n, k):
		d = {}
		(count, l, r) = (0, 0, 0)
		while r < n:
			if arr[r] not in d:
				d[arr[r]] = 0
			d[arr[r]] += 1
			while len(d) > k:
				if arr[l] not in d:
					d[arr[l]] = 0
				d[arr[l]] -= 1
				if d[arr[l]] <= 0:
					del d[arr[l]]
				l += 1
			count += r - l + 1
			r += 1
		return count

	def subarrayCount(self, arr, N, k):
		return self.solve(arr, N, k) - self.solve(arr, N, k - 1)


class Solution:

	def subarrayCount(self, arr, N, k):

		def count(a, k):
			i = 0
			j = 0
			d = {}
			m = 0
			while j < len(a):
				if a[j] in d:
					d[a[j]] += 1
				else:
					d[a[j]] = 1
				while len(d) > k:
					d[a[i]] -= 1
					if d[a[i]] == 0:
						del d[a[i]]
					i += 1
				m += j - i + 1
				j += 1
			return m
		return count(arr, k) - count(arr, k - 1)


class Solution:

	def subarrayCount(self, arr, N, k):
		return self.k_count(arr, N, k) - self.k_count(arr, N, k - 1)

	def k_count(self, arr, N, k):
		dic = dict()
		(i, j) = (0, 0)
		cnt = 0
		while j < N:
			if arr[j] in dic:
				dic[arr[j]] += 1
			else:
				dic[arr[j]] = 1
			while len(dic) > k:
				dic[arr[i]] -= 1
				if dic[arr[i]] == 0:
					del dic[arr[i]]
				i += 1
			cnt += j - i + 1
			j += 1
		return cnt


from collections import defaultdict

class Solution:

	def subarrayCount(self, arr, N, k):

		def atmost(k):
			(l, count, d) = (0, 0, defaultdict(int))
			for (r, v) in enumerate(arr):
				d[v] += 1
				while len(d) > k:
					d[arr[l]] -= 1
					if d[arr[l]] == 0:
						del d[arr[l]]
					l += 1
				count += r - l + 1
			return count
		return atmost(k) - atmost(k - 1)


from collections import defaultdict

class Solution:

	def subarrayCount(self, arr, N, k):
		d = defaultdict(lambda : 0)
		i = 0
		j = 0
		count = 0
		for item in arr:
			while i < N and len(d) < k:
				d[arr[i]] += 1
				i += 1
			while j < N and arr[j] in d:
				j += 1
			if len(d) == k:
				count += j - i + 1
			d[item] -= 1
			if d[item] == 0:
				del d[item]
		return count


class Solution:

	def subarrayCount(self, arr, N, k):

		def atmost(arr, N, k):
			count = 0
			si = ei = 0
			dic = {}
			while ei < N:
				if arr[ei] not in dic:
					dic[arr[ei]] = 0
				dic[arr[ei]] += 1
				while len(dic) > k:
					dic[arr[si]] -= 1
					if dic[arr[si]] == 0:
						del dic[arr[si]]
					si += 1
				count += ei - si + 1
				ei += 1
			return count
		return atmost(arr, N, k) - atmost(arr, N, k - 1)


class Solution:

	def subarrayCount(self, arr, N, k):

		def total(count):
			if count == 0:
				return 0
			res = 0
			i = 0
			c = 0
			d = {}
			for j in range(N):
				if arr[j] not in d or d[arr[j]] == 0:
					d[arr[j]] = 1
					c += 1
				else:
					d[arr[j]] += 1
				if c <= count:
					res += j - i + 1
				else:
					while i < N and i <= j and (c > count):
						d[arr[i]] -= 1
						if d[arr[i]] == 0:
							c -= 1
						i += 1
					res += j - i + 1
			return res
		return total(k) - total(k - 1)


from collections import defaultdict

class Solution:

	def subarrayCount(self, nums, N, k):

		def atmostK(arr, k):
			s = res = 0
			d = defaultdict(int)
			for e in range(len(arr)):
				d[arr[e]] += 1
				while len(d) > k:
					d[arr[s]] -= 1
					if d[arr[s]] == 0:
						del d[arr[s]]
					s += 1
				res += e - s + 1
			return res
		return atmostK(nums, k) - atmostK(nums, k - 1)


from collections import defaultdict

def countatmostk(arr, n, k):
	start = 0
	ans = 0
	c = 0
	dic = defaultdict(lambda : 0)
	for i in range(n):
		if dic[arr[i]] == 0:
			c += 1
		dic[arr[i]] += 1
		while c > k:
			dic[arr[start]] -= 1
			if dic[arr[start]] == 0:
				c -= 1
			start += 1
		ans += i - start + 1
	return ans

class Solution:

	def subarrayCount(self, arr, N, k):
		return countatmostk(arr, N, k) - countatmostk(arr, N, k - 1)


class Solution:

	def subarrayCount(self, arr, N, k):

		def atmost(arr, k):
			(l, r, count) = (0, 0, 0)
			mp = {}
			while r < len(arr):
				mp[arr[r]] = 1 + mp.get(arr[r], 0)
				while len(mp) > k:
					mp[arr[l]] -= 1
					if mp[arr[l]] == 0:
						mp.pop(arr[l])
					l += 1
				count += r - l + 1
				r += 1
			return count
		return atmost(arr, k) - atmost(arr, k - 1)


from collections import defaultdict

class Solution:

	def subarrayCount(self, arr, N, k):

		def countSubarraywithAtmostK(K):
			left = 0
			count = 0
			dicti = defaultdict(int)
			for right in range(N):
				if dicti[arr[right]] == 0:
					K -= 1
				dicti[arr[right]] += 1
				while K < 0:
					dicti[arr[left]] -= 1
					if dicti[arr[left]] == 0:
						K += 1
					left += 1
				count += right - left + 1
			return count
		return countSubarraywithAtmostK(k) - countSubarraywithAtmostK(k - 1)


from collections import Counter

class Solution:

	def subarrayCount(self, A, N, B):
		return self.helper(A, B) - self.helper(A, B - 1)

	def helper(self, arr, k):
		count = Counter()
		res = i = 0
		for j in range(len(arr)):
			if count[arr[j]] == 0:
				k -= 1
			count[arr[j]] += 1
			while k < 0:
				count[arr[i]] -= 1
				if count[arr[i]] == 0:
					k += 1
				i += 1
			res += j - i + 1
		return res


class Solution:

	def subarrayCount(self, arr, N, k):

		def solve(r):
			st = 0
			d = {}
			ans = 0
			for i in range(N):
				if arr[i] in d:
					d[arr[i]] += 1
				else:
					d[arr[i]] = 1
				while len(d) > r:
					d[arr[st]] -= 1
					if d[arr[st]] == 0:
						del d[arr[st]]
					st += 1
				ans += i - st + 1
			return ans
		return solve(k) - solve(k - 1)


class Solution:

	def count(self, s, n, k):
		m = {}
		j = 0
		c = 0
		for i in range(n):
			if s[i] in m:
				m[s[i]] += 1
			else:
				m[s[i]] = 1
			while len(m) > k:
				m[s[j]] -= 1
				if m[s[j]] == 0:
					del m[s[j]]
				j += 1
			c += i - j
		return c

	def subarrayCount(self, arr, N, k):
		return self.count(arr, N, k) - self.count(arr, N, k - 1)


class Solution:

	def subarrayCount(self, s, N, k):
		if k == 1:
			n = len(s)
			c = 1
			f = 0
			for i in range(n - 1):
				if s[i] == s[i + 1]:
					c += 1
				else:
					f += c * (c + 1) // 2
					c = 1
			f += c * (c + 1) // 2
			return f
		m1 = {}
		m2 = {}
		ism = -1
		ib = -1
		j = -1
		c = 0
		n = len(s)
		while True:
			f1 = 0
			f2 = 0
			f3 = 0
			while ib < n - 1:
				f1 = 1
				ib += 1
				if s[ib] in m1:
					m1[s[ib]] += 1
				else:
					m1[s[ib]] = 1
				if len(m1) == k + 1:
					del m1[s[ib]]
					ib -= 1
					break
			while ism < n - 1:
				f2 = 1
				ism += 1
				if s[ism] in m2:
					m2[s[ism]] += 1
				else:
					m2[s[ism]] = 1
				if len(m2) == k:
					del m2[s[ism]]
					ism -= 1
					break
			while j < ism:
				f3 = 1
				if len(m1) == k and len(m2) == k - 1:
					c += ib - ism
				j += 1
				g = s[j]
				m1[g] -= 1
				if m1[g] == 0:
					del m1[g]
				m2[g] -= 1
				if m2[g] == 0:
					del m2[g]
				if len(m1) < k or len(m2) < k - 1:
					break
			if f1 == 0 and f2 == 0 and (f3 == 0):
				break
		return c