Given an array nums of n elements and q queries . Each query consists of two integers l and r . You task is to find the number of elements of nums[] in range [l,r] which occur atleast k times.
 
Example 1:
Input: nums = {1,1,2,1,3}, Queries = {{1,5},
{2,4}}, k = 1
Output: {3,2}
Explanation: For the 1st query, from l=1 to r=5
1, 2 and 3 have the frequency atleast 1.
For the second query, from l=2 to r=4, 1 and 2 have 
the frequency atleast 1.
 
Example 1:
Input: nums = {1,2,3,1}, Queries = {{1,4},
{2,4},{4,4}, k = 2
Output: {1,0,0}
Explanation: For the 1st query, from l=1 to r=4
1 have the frequency atleast 2.
For the second query, from l=2 to r=4, no number has 
the frequency atleast 2.
For the third query, from l=4 to r=4, no number has 
the frequency atleast 2.
 
Your Task:
Your task is to complete the function solveQueries() which takes nums, Queries and k as input parameter and returns a list containg the answer for each query.
 
Expected Time Complexity: O(n*sqrt(n)*log(n))
Expected Space Compelxity: O(n)
 
Constraints:
1 <= n, no of Queries, k <= 10^{4}
1 <= nums[i] <= 10^{3}
1 <= Queries[i][0] <= Queries[i][1] <= n

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Square root algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

	def solveQueries(self, nums, Queries, k):

		#Code here

Solutions:
import math

class Solution:

	def solveQueries(self, nums, Queries, k):
		answers = [0] * len(Queries)
		count = {}
		n = int(math.sqrt(len(nums))) + 1
		q = list(enumerate(Queries))
		q.sort(key=lambda a: [int(a[1][0] / n), -a[1][1]])
		currentL = 0
		currentR = -1
		ans = 0
		for i in q:
			left = i[1][0] - 1
			right = i[1][1] - 1
			while currentR < right:
				currentR += 1
				count[nums[currentR]] = count.get(nums[currentR], 0) + 1
				if count[nums[currentR]] == k:
					ans += 1
			while currentL < left:
				count[nums[currentL]] -= 1
				if count[nums[currentL]] == k - 1:
					ans -= 1
				currentL += 1
			while currentR > right:
				count[nums[currentR]] -= 1
				if count[nums[currentR]] == k - 1:
					ans -= 1
				currentR -= 1
			while currentL > left:
				currentL -= 1
				count[nums[currentL]] = count.get(nums[currentL], 0) + 1
				if count[nums[currentL]] == k:
					ans += 1
			answers[i[0]] = ans
		return answers


from collections import Counter

class query:

	def __init__(self, L=float('inf'), R=float('inf'), i=0):
		self.L = L
		self.R = R
		self.i = i

class Solution:

	def add(self, p, k):
		self.cnt[self.a[p]] += 1
		if self.cnt[self.a[p]] == k:
			self.answer += 1

	def subtract(self, p, k):
		self.cnt[self.a[p]] -= 1
		if self.cnt[self.a[p]] == k - 1:
			self.answer -= 1

	def solveQueries(self, nums, Queries, k):
		n = len(nums)
		m = len(Queries)
		self.a = [0] * 10005
		self.cnt = [0] * 10005
		q = [query() for _ in range(10005)]
		self.answer = 0
		for i in range(n):
			self.a[i] = nums[i]
		for i in range(m):
			q[i].L = Queries[i][0]
			q[i].R = Queries[i][1]
			q[i].L -= 1
			q[i].R -= 1
			q[i].i = i
		q.sort(key=lambda x: (x.L // 318, x.R))
		c_l = 0
		c_r = 0
		ans = [0] * m
		for i in range(m):
			l = q[i].L
			r = q[i].R
			while c_l < l:
				self.subtract(c_l, k)
				c_l += 1
			while c_l > l:
				self.add(c_l - 1, k)
				c_l -= 1
			while c_r <= r:
				self.add(c_r, k)
				c_r += 1
			while c_r > r + 1:
				self.subtract(c_r - 1, k)
				c_r -= 1
			ans[q[i].i] = self.answer
		return ans


class Solution:

	def solveQueries(self, nums, Queries, k):
		sor = sorted(range(q), key=lambda x: Queries[x][1])
		(sq, ret) = (int(n ** 0.5), [0] * q)
		for i in range(sq + 2):
			(curl, curr) = (min(i * sq, n - 1), min((i + 1) * sq - 1, n - 1))
			(freq, num) = ([0] * (10 ** 3 + 1), 0)
			for j in range(curl, curr + 1):
				freq[nums[j]] += 1
				num += freq[nums[j]] == k
			for j in range(q):
				(l, r) = Queries[sor[j]]
				l -= 1
				r -= 1
				if i * sq <= l < (i + 1) * sq:
					while curl < l:
						num -= freq[nums[curl]] == k
						freq[nums[curl]] -= 1
						curl += 1
					while curl > l:
						curl -= 1
						freq[nums[curl]] += 1
						num += freq[nums[curl]] == k
					while curr < r:
						curr += 1
						freq[nums[curr]] += 1
						num += freq[nums[curr]] == k
					while curr > r:
						num -= freq[nums[curr]] == k
						freq[nums[curr]] -= 1
						curr -= 1
					ret[sor[j]] = num
		return list(ret)


import math

class Solution:

	def solveQueries(self, nums, Queries, k):

		def compare(q1, q2):
			pass
		ans = [0] * len(Queries)
		d = {}
		n = int(math.sqrt(len(nums))) + 1
		q = list(enumerate(Queries))
		q.sort(key=lambda a: [int(a[1][0] / n), -a[1][1]])
		c_l = 0
		c_r = -1
		c_a = 0
		for i in q:
			l = i[1][0] - 1
			r = i[1][1] - 1
			while c_r < r:
				c_r += 1
				d[nums[c_r]] = d.get(nums[c_r], 0) + 1
				if d[nums[c_r]] == k:
					c_a += 1
			while c_l < l:
				d[nums[c_l]] -= 1
				if d[nums[c_l]] == k - 1:
					c_a -= 1
				c_l += 1
			while c_r > r:
				d[nums[c_r]] -= 1
				if d[nums[c_r]] == k - 1:
					c_a -= 1
				c_r -= 1
			while c_l > l:
				c_l -= 1
				d[nums[c_l]] = d.get(nums[c_l], 0) + 1
				if d[nums[c_l]] == k:
					c_a += 1
			ans[i[0]] = c_a
		return ans


from math import ceil
from collections import defaultdict

class Solution:

	def solveQueries(self, x, q, k):
		block_size = ceil(n ** 0.5)
		q = [(q[i][0] - 1, q[i][1] - 1, i) for i in range(len(q))]
		q.sort(key=lambda i: (i[0] // block_size, i[1], i[0]) if i[0] // block_size % 2 == 0 else (i[0] // block_size, -i[1], i[0]))
		f = [0 for i in range(max(x) + 1)]
		left = 0
		right = 0
		f[x[0]] += 1
		count = 1 if k == 1 else 0
		res = [0 for i in range(len(q))]
		for (a, b, c) in q:
			while left < a:
				f[x[left]] -= 1
				if f[x[left]] == k - 1:
					count -= 1
				left += 1
			while left > a:
				left -= 1
				f[x[left]] += 1
				if f[x[left]] == k:
					count += 1
			while right > b:
				f[x[right]] -= 1
				if f[x[right]] == k - 1:
					count -= 1
				right -= 1
			while right < b:
				right += 1
				f[x[right]] += 1
				if f[x[right]] == k:
					count += 1
			res[c] = count
		return res


from collections import Counter

class Solution:

	def solveQueries(self, nums, Queries, k):
		ans = []
		for i in Queries:
			count = 0
			frequency = Counter(nums[i[0] - 1:i[1]])
			for j in frequency.values():
				if j >= k:
					count += 1
			ans.append(count)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, q, k) = input().split()
		n = int(n)
		q = int(q)
		k = int(k)
		nums = list(map(int, input().split()))
		Queries = []
		for _ in range(q):
			Queries.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.solveQueries(nums, Queries, k)
		for _ in ans:
			print(_)


from collections import Counter

class Solution:

	def solveQueries(self, nums, Queries, k):
		ans = []
		for q in Queries:
			dic = {}
			cnt = 0
			freq = Counter(nums[q[0] - 1:q[1]])
			for v in freq.values():
				if v >= k:
					cnt += 1
			ans.append(cnt)
		return ans


from collections import Counter

class Solution:

	def solveQueries(self, nums, Queries, k):
		ans = []
		for i in Queries:
			count = 0
			freq = Counter(nums[i[0] - 1:i[1]])
			for j in freq.values():
				if j >= k:
					count += 1
			ans.append(count)
		return ans


from collections import Counter as Ctr

class Solution:

	def solveQueries(self, arr, query, k):
		return [len([_ for y in dict(Ctr(arr[x[0] - 1:x[1]])).values() if y >= k]) for x in query]


from collections import Counter

class Solution:

	def solveQueries(self, arr, query, k):
		return [sum((1 for y in dict(Counter(arr[x[0] - 1:x[1]])).values() if y >= k)) for x in query]


from collections import Counter

class Solution:

	def solveQueries(self, arr, query, k):
		ans = []
		for x in query:
			l = dict(Counter(arr[x[0] - 1:x[1]]))
			temp = sum((1 for x in l.values() if x >= k))
			ans.append(temp)
		return ans


from collections import Counter

class Solution:

	def solveQueries(self, nums, Queries, k):
		m = []
		for x in Queries:
			r = 0
			p = nums[x[0] - 1:x[1]]
			l = dict(Counter(p))
			for x in l:
				if l[x] >= k:
					r = r + 1
			m.append(r)
		return m