Given N numbers in an array. Your task is to keep at-most K numbers at the top (According to their frequency).  We basically need to print top k numbers when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency.
Example 1:
Input:
N=5, K=4
arr[] = {5, 2, 1, 3, 2} 
Output: 5 2 5 1 2 5 1 2 3 5 2 1 3 5 
Explanation:
Firstly their was 5 whose frequency
is max till now. so print 5.
Then 2 , which is smaller than 5 but
their frequency is same so print 2 5.
Then 1, which is smallet among all the
number arrived, so print 1 2 5.
Then 3 , so print 1 2 3 5
Then again 2, which has the highest
frequency among all number so 2 1 3 5.
Example 2:
Input:
N=5, K=4
arr[] = {5, 2, 1, 3, 4} 
Output: 5 2 5 1 2 5 1 2 3 5 1 2 3 4 
Explanation:
Firstly their was 5 whose frequency is
max till now. so print 5.
Then 2 , which is smaller than 5 but
their frequency is same so print 2 5.
Then 1, Which is smallest among all the
number arrived, so print 1 2 5.
Then 3 , so print 1 2 3 5.
Then 4, so 1 2 3 4 as K is 4 so print
at-most k elements.
 
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function kTop() that takes array a, integer n and integer k as parameters and returns the array that contains our desired output.
 
Expected Time Complexity: O(N*K).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N,K ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def kTop(self,a, n, k):
        #code here.

Solutions:
class Solution:

	def kTop(self, a, n, k):
		top = [0 for i in range(k + 1)]
		freq = {i: 0 for i in range(k + 1)}
		ans = []
		for m in range(n):
			if a[m] in freq.keys():
				freq[a[m]] += 1
			else:
				freq[a[m]] = 1
			top[k] = a[m]
			i = top.index(a[m])
			i -= 1
			while i >= 0:
				if freq[top[i]] < freq[top[i + 1]]:
					t = top[i]
					top[i] = top[i + 1]
					top[i + 1] = t
				elif freq[top[i]] == freq[top[i + 1]] and top[i] > top[i + 1]:
					t = top[i]
					top[i] = top[i + 1]
					top[i + 1] = t
				else:
					break
				i -= 1
			i = 0
			while i < k and top[i] != 0:
				ans.append(top[i])
				i += 1
		return ans


class Solution:

	def kTop(self, a, n, k):
		ans = []
		freq = {}
		pos = {}
		curr = []
		for item in a:
			if item not in pos:
				curr.append(item)
				freq[item] = 1
				pos[item] = len(curr) - 1
			else:
				freq[item] += 1
			for j in range(pos[item], 0, -1):
				if freq[curr[j - 1]] < freq[curr[j]] or (freq[curr[j - 1]] == freq[curr[j]] and curr[j - 1] > curr[j]):
					(curr[j - 1], curr[j]) = (curr[j], curr[j - 1])
					pos[curr[j - 1]] = j - 1
					pos[curr[j]] = j
				else:
					break
			ans.extend(curr[:k])
		return ans


from collections import defaultdict
import heapq

class Solution:

	def kTop(self, a, n, k):
		res = []
		hp1 = []
		c = defaultdict(int)
		for i in range(n):
			c[a[i]] += 1
			heapq.heappush(hp1, (-c[a[i]], a[i]))
			hp2 = []
			count = 0
			vis = set()
			while hp1 and count < k:
				(freq, num) = heapq.heappop(hp1)
				if num not in vis:
					count += 1
					vis.add(num)
					res.append(num)
					heapq.heappush(hp2, (freq, num))
			while hp1:
				(freq, num) = heapq.heappop(hp1)
				heapq.heappush(hp2, (freq, num))
			hp1 = hp2
		return res


from functools import cmp_to_key

class Solution:

	def kTop(self, a, n, k):

		def comp(a, b):
			if a[0] == b[0]:
				if a[1] > b[1]:
					return 1
				else:
					return -1
			elif a[0] < b[0]:
				return 1
			else:
				return -1
		mapper = dict()
		ans = list()
		for i in a:
			mapper[i] = [1 + mapper.get(i, [0, 0])[0], i]
			stack = list()
			for vals in mapper.values():
				stack.append(vals)
			letter_cmp_key = cmp_to_key(comp)
			stack = sorted(stack, key=letter_cmp_key)
			vals = [x[1] for x in stack[:k]]
			ans.extend(vals)
		return ans


class Solution:

	def kTop(self, a, n, k):
		d = {}
		ans = []
		max_fre = 1
		for i in a:
			if i in d:
				d[i] += 1
				if d[i] > max_fre:
					max_fre = d[i]
			else:
				d[i] = 1
			anstemp = []
			for j in range(max_fre, 0, -1):
				temp = []
				for g in d:
					if d[g] == j:
						temp.append(g)
				temp.sort()
				anstemp.extend(temp)
			ans.extend(anstemp[:k])
		return ans


from collections import defaultdict

class Solution:

	def kTop(self, a, n, k):
		results = []
		pairs = []
		d = defaultdict(int)
		for value in a:
			old = d[value]
			d[value] = old + 1
			try:
				pairs.remove((old, -value))
			except ValueError:
				pass
			pairs.append((d[value], -value))
			for pos in range(len(pairs) - 2, -1, -1):
				if pairs[pos] < pairs[pos + 1]:
					(pairs[pos], pairs[pos + 1]) = (pairs[pos + 1], pairs[pos])
			if len(pairs) > k:
				pairs.pop()
			results += [-pair[1] for pair in pairs]
		return results


from collections import defaultdict
from functools import cmp_to_key

class Solution:

	def kTop(self, a, n, k):

		def comp(x, y):
			if x[1] == y[1]:
				if x[0] < y[0]:
					return -1
				else:
					return 1
			elif x[1] > y[1]:
				return -1
			else:
				return 1
		v = []
		m = defaultdict(int)
		for i in range(n):
			m[a[i]] += 1
			ans = []
			for it in m:
				ans.append([it, m[it]])
			ans.sort(key=cmp_to_key(comp))
			for i in range(len(ans)):
				if i >= k:
					break
				v.append(ans[i][0])
		return v


class Solution:

	def kTop(self, arr, n, k):
		import bisect
		res = []
		from collections import defaultdict
		freq = defaultdict(int)
		s = defaultdict(list)
		for i in range(n):
			if arr[i] in s[freq[arr[i]]]:
				s[freq[arr[i]]].remove(arr[i])
			freq[arr[i]] += 1
			s[freq[arr[i]]].append(arr[i])
			count = 0
			for j in sorted(s.keys(), reverse=True):
				for l in sorted(s[j]):
					res.append(l)
					count += 1
					if count == k:
						break
				if count == k:
					break
		return res


class Solution:

	def kTop(self, arr, n, k):
		ans = []
		top = [0] * (k + 1)
		freq = {i: 0 for i in range(k + 1)}
		for i in range(n):
			try:
				freq[arr[i]] += 1
			except:
				freq[arr[i]] = 1
			top[k] = arr[i]
			index = top.index(arr[i]) - 1
			while index >= 0:
				if freq[top[index]] < freq[top[index + 1]]:
					(top[index], top[index + 1]) = (top[index + 1], top[index])
				elif freq[top[index]] == freq[top[index + 1]] and top[index] > top[index + 1]:
					(top[index], top[index + 1]) = (top[index + 1], top[index])
				else:
					break
				index -= 1
			for i in range(len(top)):
				if top[i] != 0 and i < k:
					ans.append(top[i])
		return ans


from collections import defaultdict

class Solution:

	def kTop(self, a, n, k):
		freq = defaultdict(int)
		ans = []
		for i in range(n):
			freq[a[i]] += 1
			ans.extend(self.getSortedByFreq(freq)[:k])
		return ans

	def getSortedByFreq(self, freq):
		arr = list(freq.keys())
		arr.sort(key=lambda i: (-freq[i], i))
		return arr


class Solution:

	def kTop(self, a, n, k):
		d = {}
		ind = 0
		from queue import PriorityQueue
		pq = PriorityQueue()
		ans = []
		while ind < n:
			val = a[ind]
			d[val] = d.get(val, 0) + 1
			for i in d:
				f1 = -d[i]
				f2 = i
				pq.put((f1, f2))
			t = k
			while pq.qsize() != 0:
				(s, b) = pq.get()
				if k > 0:
					ans.append(b)
					k -= 1
			k = t
			ind += 1
		return ans


import heapq

class Solution:

	def kTop(self, a, n, k):
		(pq1, pq2, res) = ([], [], [])
		dic = {}
		change = 1
		for i in range(0, n):
			if change:
				if a[i] in dic:
					heapq.heappush(pq1, [-1 * (1 + dic[a[i]]), a[i]])
					dic[a[i]] += 1
				else:
					heapq.heappush(pq1, [-1, a[i]])
					dic[a[i]] = 1
				j = 0
				while len(pq1) and j < k:
					(freq, val) = heapq.heappop(pq1)
					if -1 * dic[val] == freq:
						heapq.heappush(pq2, [freq, val])
						res.append(val)
						j += 1
				change = 0
				pq1 = []
			else:
				if a[i] in dic:
					heapq.heappush(pq2, [-1 * (1 + dic[a[i]]), a[i]])
					dic[a[i]] += 1
				else:
					heapq.heappush(pq2, [-1, a[i]])
					dic[a[i]] = 1
				j = 0
				while len(pq2) and j < k:
					(freq, val) = heapq.heappop(pq2)
					if -1 * dic[val] == freq:
						heapq.heappush(pq1, [freq, val])
						res.append(val)
						j += 1
				change = 1
				pq2 = []
		return res


import collections, heapq, copy

class Solution:

	def kTop(self, a, n, k):
		maxHeap = []
		heapq.heapify(maxHeap)
		cnt = collections.defaultdict(lambda : 0)
		ans = []
		for num in a:
			if (cnt[num], -num) in maxHeap:
				maxHeap.remove((cnt[num], -num))
				heapq.heapify(maxHeap)
			cnt[num] += 1
			heapq.heappush(maxHeap, (cnt[num], -num))
			if len(maxHeap) > k:
				heapq.heappop(maxHeap)
			temp_heap = copy.deepcopy(maxHeap)
			temp = []
			while temp_heap:
				temp.append(-heapq.heappop(temp_heap)[1])
			ans += temp[::-1]
		return ans


import heapq

class Solution:

	def kTop(self, arr, n, k):
		dic = {}
		heap = []
		ans = []
		for ele in arr:
			dic[ele] = dic.get(ele, 0) + 1
			for (ele, freq) in dic.items():
				heapq.heappush(heap, (-freq, ele))
			count = 0
			while heap and count < k:
				val = heapq.heappop(heap)
				ans.append(val[1])
				count += 1
		return ans
t = int(input())
for _ in range(0, t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ob = Solution()
	ans = ob.kTop(a, n, k)
	print(*ans)


class Solution:

	def kTop(self, a, n, k):
		d = {}
		for i in a:
			if i not in d:
				d[i] = 0
		st = ''

		def aa(a, d, st, K):
			s = []
			for i in a:
				d[i] = d[i] + 1
			for (k, v) in d.items():
				s.append([k] * v)
			s.sort()
			aa = sorted(s, key=len, reverse=True)
			ruk = 0
			for i in aa:
				ruk += 1
				for j in i:
					st = st + str(j)
					st = st + ' '
					break
				if ruk >= K:
					break
			return st
		for i in range(1, n + 1):
			st = aa(a[:i], d, st, k)
			d = {}
			for i in a:
				if i not in d:
					d[i] = 0
		return st.split()
t = int(input())
for _ in range(0, t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ob = Solution()
	ans = ob.kTop(a, n, k)
	print(*ans)


from collections import defaultdict

class Solution:

	def kTop(self, a, n, k):
		res = []
		freq = defaultdict(int)
		top = [0 for i in range(k + 1)]
		for m in range(n):
			freq[a[m]] += 1
			top[k] = a[m]
			i = top.index(a[m])
			i -= 1
			while i >= 0:
				if freq[top[i]] < freq[top[i + 1]]:
					(top[i], top[i + 1]) = (top[i + 1], top[i])
				elif freq[top[i]] == freq[top[i + 1]] and top[i] > top[i + 1]:
					(top[i], top[i + 1]) = (top[i + 1], top[i])
				else:
					break
				i -= 1
			i = 0
			while i < k and top[i] != 0:
				res.append(top[i])
				i += 1
		return res


from collections import defaultdict

class Solution:

	def kTop(self, a, n, k):
		arrk = []

		def delete(x):
			for i in range(len(arrk)):
				if arrk[i][1] == x:
					for j in range(i + 1, len(arrk)):
						arrk[j - 1] = arrk[j]
					arrk.pop()
					break
			return
		res = []
		freq = defaultdict(int)
		for i in a:
			freq[i] += 1
			delete(i)
			arrk.append([freq[i], i])
			for j in range(len(arrk) - 2, -1, -1):
				if arrk[j][0] > arrk[j + 1][0]:
					break
				if arrk[j][0] == arrk[j + 1][0] and arrk[j][1] < arrk[j + 1][1]:
					break
				(arrk[j], arrk[j + 1]) = (arrk[j + 1], arrk[j])
			if len(arrk) > k:
				arrk.pop()
			ans = [x[1] for x in arrk]
			res += ans
		return res


import heapq

class Solution:

	def kTop(self, a, n, k):
		freq = dict()
		ans = []
		for i in range(n):
			if not a[i] in freq:
				freq[a[i]] = 1
			else:
				freq[a[i]] += 1
			rev_freq = []
			if len(freq) < k:
				for key in freq:
					rev_freq.append([-freq[key], key])
				heapq.heapify(rev_freq)
				for _ in range(len(rev_freq)):
					ans.append(heapq.heappop(rev_freq)[1])
			else:
				for key in freq:
					rev_freq.append([-freq[key], key])
				heapq.heapify(rev_freq)
				for _ in range(k):
					ans.append(heapq.heappop(rev_freq)[1])
		return ans


class Solution:

	def kTop(self, a, n, k):
		freq = {}
		temp = []
		ans = []
		for v in a:
			if v not in freq:
				freq[v] = 1
				temp.append(v)
				i = len(temp) - 1
			else:
				freq[v] += 1
				i = temp.index(v)
			while i > 0:
				if freq[temp[i]] > freq[temp[i - 1]]:
					(temp[i], temp[i - 1]) = (temp[i - 1], temp[i])
					i -= 1
				elif freq[temp[i]] == freq[temp[i - 1]]:
					if temp[i] < temp[i - 1]:
						(temp[i], temp[i - 1]) = (temp[i - 1], temp[i])
					i -= 1
				else:
					break
			if len(temp) <= k:
				ans.extend(temp)
			else:
				ans.extend(temp[:k])
		return ans


class Solution:

	def kTop(self, a, n, k):
		res = []
		top = [0 for i in range(k + 1)]
		freq = {i: 0 for i in range(k + 1)}
		for i in range(n):
			freq[a[i]] = 1 + freq.get(a[i], 0)
			top[k] = a[i]
			e = top.index(a[i])
			e = e - 1
			while e >= 0:
				if freq[top[e]] < freq[top[e + 1]]:
					t = top[e]
					top[e] = top[e + 1]
					top[e + 1] = t
				elif freq[top[e]] == freq[top[e + 1]] and top[e] > top[e + 1]:
					t = top[e]
					top[e] = top[e + 1]
					top[e + 1] = t
				else:
					break
				e -= 1
			e = 0
			while e < k and top[e] != 0:
				res.append(top[e])
				e += 1
		return res


class Solution:

	def kTop(self, a, n, kk):
		d = {}
		ar = []
		ans = []
		for x in a:
			if x in d:
				d[x][0] += 1
				k = d[x][1]
				while k >= 1:
					v = ar[k - 1]
					if d[v][0] < d[x][0]:
						ar[k] = ar[k - 1]
						d[v][1] = k
					elif d[v][0] == d[x][0] and v > x:
						ar[k] = ar[k - 1]
						d[v][1] = k
					else:
						break
					k -= 1
				ar[k] = x
				d[x][1] = k
			else:
				ar.append(x)
				d[x] = [1, None]
				k = len(ar) - 1
				while k >= 1:
					v = ar[k - 1]
					if v > x and d[v][0] <= d[x][0]:
						ar[k] = ar[k - 1]
						d[v][1] = k
					else:
						break
					k -= 1
				ar[k] = x
				d[x][1] = k
			ans.extend(ar[:kk])
		return ans


class Solution:

	def kTop(self, arr, n, k):
		mapx = {}
		ans = []
		for i in range(n):
			if arr[i] not in mapx:
				mapx[arr[i]] = 1
			else:
				mapx[arr[i]] += 1
			q = list(mapx.items())
			q.sort()
			q.sort(reverse=True, key=lambda x: x[1])
			i = 0
			while q and i < k:
				tup = q.pop(0)
				ans.append(tup[0])
				i += 1
		return ans


from collections import defaultdict
from collections import OrderedDict

class Solution:

	def kTop(self, arr, n, k):
		pq = []
		ans = []
		max_freq = 0
		mapp = {}
		for i in range(n):
			if a[i] not in mapp:
				mapp[a[i]] = 1
			else:
				mapp[a[i]] += 1
			mapp = OrderedDict(sorted(mapp.items()))
			if max_freq < mapp[a[i]]:
				max_freq = mapp[a[i]]
			freq = max_freq
			j = 0
			while freq != 0 and j != k:
				for key in mapp:
					if mapp[key] == freq:
						ans.append(key)
						j += 1
						if j == k:
							break
				freq -= 1
		return ans


from heapq import heapify, heappop, heappush

class Solution:

	def kTop(self, a, n, k):
		freqs = {}
		maxFreq = 0
		h = []
		heapify(h)
		arr = []
		for i in range(n):
			if a[i] not in freqs:
				freqs[a[i]] = 1
			else:
				freqs[a[i]] += 1
			for (key, val) in freqs.items():
				heappush(h, [-val, key])
			cnt = 0
			while h and cnt < k:
				(val, key) = heappop(h)
				arr.append(key)
				cnt += 1
		return arr


from collections import Counter

class Solution:

	def kTop(self, a, n, k):
		top = [0 for i in range(k + 1)]
		freq = Counter()
		res = []
		for m in range(n):
			freq[a[m]] += 1
			top[k] = a[m]
			i = top.index(a[m])
			i -= 1
			while i >= 0:
				if freq[top[i]] < freq[top[i + 1]]:
					(top[i], top[i + 1]) = (top[i + 1], top[i])
				elif freq[top[i]] == freq[top[i + 1]] and top[i] > top[i + 1]:
					(top[i], top[i + 1]) = (top[i + 1], top[i])
				i -= 1
			i = 0
			while i < k and top[i] != 0:
				res.append(top[i])
				i += 1
		return res


from collections import defaultdict
from heapq import *

class Solution:

	def kTop(self, a, n, k):
		ans = []
		count = defaultdict(int)
		for i in range(n):
			count[a[i]] += 1
			heap = [(-freq, key) for (key, freq) in count.items()]
			heapify(heap)
			for j in range(k):
				(c, p) = heappop(heap)
				ans.append(p)
				if not heap:
					break
		return ans


from collections import defaultdict
from heapq import *

class Solution:

	def kTop(self, a, n, k):
		res = []
		counts = defaultdict(int)
		for i in range(n):
			counts[a[i]] += 1
			heap = [(-v, k) for (k, v) in counts.items()]
			heapify(heap)
			for i in range(k):
				(count, key) = heappop(heap)
				res.append(key)
				if not heap:
					break
		return res


class Solution:

	def kTop(self, arr, n, k):
		k_arr = []
		freq = {}
		out = []
		for num in arr:
			if num in freq:
				freq[num] += 1
			else:
				freq[num] = 1
				k_arr.append(num)
			curr_index = len(k_arr) - 1
			for i in reversed(range(1, len(k_arr))):
				if freq[k_arr[i]] > freq[k_arr[i - 1]]:
					(k_arr[i], k_arr[i - 1]) = (k_arr[i - 1], k_arr[i])
			for i in reversed(range(1, len(k_arr))):
				if freq[k_arr[i]] == freq[k_arr[i - 1]] and k_arr[i] < k_arr[i - 1]:
					(k_arr[i], k_arr[i - 1]) = (k_arr[i - 1], k_arr[i])
			for i in range(len(k_arr)):
				if i < k:
					out.append(k_arr[i])
		return out


class Solution:

	def kTop(self, a, n, k):

		class LLNode:

			def __init__(self, key, val):
				self.key = key
				self.val = val
				self.prev = None
				self.next = None

		class LL:

			def __init__(self):
				self.head = None
				self.tail = None

			def append(self, node):
				if self.head is None:
					self.head = node
					self.tail = node
				else:
					self.tail.next = node
					node.prev = self.tail
					self.tail = node

			def shift(self, node):
				while True:
					if node.prev is None or node.prev.val > node.val:
						break
					if node.prev.val == node.val and node.prev.key < node.key:
						break
					prev_node = node.prev
					prev_node.next = node.next
					if not node.next is None:
						node.next.prev = prev_node
					else:
						self.tail = prev_node
					node.prev = prev_node.prev
					if not prev_node.prev is None:
						prev_node.prev.next = node
					else:
						self.head = node
					node.next = prev_node
					prev_node.prev = node

			def pprint(self, k=None):
				result = []
				n = 0
				node = self.head
				while not node is None:
					if not k is None and n >= k:
						break
					result.append(node.key)
					node = node.next
					n += 1
				return result
		result = []
		ll = LL()
		node_map = {}
		for x in a:
			if not x in node_map:
				node = LLNode(x, 1)
				ll.append(node)
				ll.shift(node)
				node_map[x] = node
			else:
				node = node_map[x]
				node.val += 1
				ll.shift(node)
			result += ll.pprint(k)
		return result


import heapq

class Solution:

	def kTop(self, a, n, k):
		ans = []
		for i in range(n):
			d = {}
			for u in a[:i + 1]:
				if u in d:
					d[u] += 1
				else:
					d[u] = 1
			l = []
			for e in d.keys():
				heapq.heappush(l, (-1 * d[e], e))
			c = 0
			while l and c != k:
				ans.append(heapq.heappop(l)[1])
				c += 1
		return ans


import heapq
from collections import Counter

class Solution:

	def kTop(self, a, n, k):
		temp = Counter()
		ans = []
		for i in a:
			temp[i] -= 1
			ref = []
			for i in temp:
				heapq.heappush(ref, [temp[i], i])
			for j in heapq.nsmallest(k, ref):
				ans.append(j[1])
		return ans


class Solution:

	def kTop(self, a, n, k):
		ans = []
		d = {}
		for i in a:
			if d.get(i) == None:
				d[i] = 0
			d[i] += 1
			g = sorted(list(d.keys()), key=lambda x: (-d[x], x))
			ans.extend(g[:k])
		return ans


import heapq

class Solution:

	def kTop(self, a, n, k):
		hashMap = {}
		arr = []
		for z in a:
			hashMap[z] = hashMap.get(z, 0) + 1
			heap = [(-freq, val) for (val, freq) in hashMap.items()]
			heapq.heapify(heap)
			n = len(heap)
			temp = k
			while heap and temp:
				arr += [heapq.heappop(heap)[1]]
				temp -= 1
		return arr


class Solution:

	def kTop(self, a, n, k):
		q = []
		for i in range(n):
			l = a[:i + 1]
			d = {}
			for i in l:
				m = l.count(i)
				if m in d:
					d[m].append(i)
				else:
					d[m] = [i]
			arr = []
			for i in d:
				arr.append(i)
			c = 0
			arr.sort(reverse=True)
			for i in arr:
				if c >= k:
					break
				p = d[i]
				p = set(p)
				p = list(p)
				p.sort()
				for j in p:
					if c >= k:
						break
					q.append(j)
					c += 1
		return q


class Solution:

	def kTop(self, a, n, k):
		vis = {}
		ans = []
		for i in range(n):
			arr = []
			temp = a[i]
			if temp in vis.keys():
				vis[temp] += 1
			else:
				vis[temp] = 1
			for key in vis.keys():
				arr.append([key, vis[key]])
			arr.sort(key=lambda x: (-x[1], x[0]))
			for t in range(len(arr)):
				if t == k:
					break
				ans.append(arr[t][0])
		return ans


def find(i, q):
	for j in range(len(q)):
		if q[j] == i:
			return j

def updateq(i, q, freqDict):
	pos = find(i, q)
	while pos > 0 and freqDict[q[pos - 1]] < freqDict[q[pos]]:
		(q[pos - 1], q[pos]) = (q[pos], q[pos - 1])
		pos -= 1
	while pos > 0 and freqDict[q[pos - 1]] == freqDict[q[pos]] and (q[pos - 1] > q[pos]):
		(q[pos - 1], q[pos]) = (q[pos], q[pos - 1])
		pos -= 1

def receive(i, q, freqDict, windDict, k):
	if i in windDict:
		freqDict[i] += 1
		updateq(i, q, freqDict)
	else:
		if i in freqDict:
			freqDict[i] += 1
		else:
			freqDict[i] = 1
		windDict[i] = 1
		q.append(i)
		updateq(i, q, freqDict)
		if len(q) > k:
			el = q.pop()
			windDict.pop(el)

def printQueue(q):
	for i in q:
		print(str(i), end=' ')

class Solution:

	def kTop(self, a, n, k):
		freqDict = {}
		windDict = {}
		q = []
		ret = ''
		for i in a:
			receive(i, q, freqDict, windDict, k)
			printQueue(q)
		return ret


class Solution:

	def kTop(self, a, n, k):
		import heapq
		dic = {}
		heap = []
		b = []
		for ele in a:
			dic[ele] = dic.get(ele, 0) + 1
			for (ele, freq) in dic.items():
				heapq.heappush(heap, (-freq, ele))
			count = 0
			while heap and count < k:
				val = heapq.heappop(heap)
				b.append(val[1])
				count += 1
		return b


from heapq import heappush, heappop

class Solution:

	def kTop(self, a, n, k):
		output = []
		counts = {}
		for i in a:
			if i in counts.keys():
				counts[i] += 1
			else:
				counts[i] = 1
			freqHeap = []
			for (key, v) in counts.items():
				if len(freqHeap) < k:
					heappush(freqHeap, (v, -key))
				else:
					top = heappop(freqHeap)
					if top[0] < v or (top[0] == v and -top[1] > key):
						heappush(freqHeap, (v, -key))
					else:
						heappush(freqHeap, top)
			outputI = []
			while len(freqHeap) > 0:
				curr = heappop(freqHeap)
				outputI.insert(0, -curr[1])
			output.extend(outputI)
		return output


from heapq import heappush, heappop

class Solution:

	def kTop(self, a, n, k):
		ret = []
		cnts = {}
		i = 0
		topk = []
		for el in a:
			if el in cnts:
				cnts[el] += 1
			else:
				cnts[el] = 1
			if not el in topk:
				topk.append(el)
			j = len(topk) - 1
			while j > 0:
				if cnts[topk[j]] > cnts[topk[j - 1]]:
					temp = topk[j]
					temp2 = topk[j - 1]
					topk[j - 1] = temp
					topk[j] = temp2
				elif cnts[topk[j]] == cnts[topk[j - 1]]:
					if topk[j] < topk[j - 1]:
						temp = topk[j]
						temp2 = topk[j - 1]
						topk[j - 1] = temp
						topk[j] = temp2
				j -= 1
			if len(topk) > k:
				topk.pop()
			ret.extend(topk)
		return ret


class Solution:

	def kTop(self, a, n, k):
		ans = []
		hashmap = {0: 0}
		temp = [0 for i in range(k + 1)]
		for i in range(n):
			if a[i] not in hashmap:
				hashmap[a[i]] = 1
			else:
				hashmap[a[i]] += 1
			temp[k] = a[i]
			j = temp.index(a[i]) - 1
			while j >= 0:
				if hashmap[temp[j]] < hashmap[temp[j + 1]]:
					(temp[j], temp[j + 1]) = (temp[j + 1], temp[j])
				elif hashmap[temp[j]] == hashmap[temp[j + 1]] and temp[j] > temp[j + 1]:
					(temp[j], temp[j + 1]) = (temp[j + 1], temp[j])
				else:
					break
				j -= 1
			e = 0
			while e < k and temp[e] != 0:
				ans.append(temp[e])
				e += 1
		return ans


class Solution:

	def kTop(self, a, n, k):
		k = min(n, k)
		ans = []
		temp = []
		mp = {}
		j = 0
		for i in range(n):
			mp[a[i]] = mp.get(a[i], 0) - 1
			if mp[a[i]] == -1:
				temp.append(a[i])
			j += 1
			temp = sorted(temp, key=lambda x: (mp[x], x))
			for p in range(min(k, len(temp))):
				ans.append(temp[p])
		return ans


from collections import defaultdict
from bisect import bisect_left

class Solution:

	def kTop(self, a, n, k):
		count = defaultdict(int)
		top = [0 for _ in range(k + 1)]
		ans = []
		for el in a:
			count[el] += 1
			top[k] = el
			i = top.index(el)
			while count[top[i]] > count[top[i - 1]] and i >= 1:
				(top[i], top[i - 1]) = (top[i - 1], top[i])
				i -= 1
			while count[top[i]] == count[top[i - 1]] and i >= 1 and (top[i] < top[i - 1]):
				(top[i], top[i - 1]) = (top[i - 1], top[i])
				i -= 1
			x = 0
			while x < k and x < len(top) and (top[x] != 0):
				ans.append(top[x])
				x += 1
		return ans


class Solution:

	def kTop(self, a, n, k):
		d = {}
		ans = []
		for i in range(n):
			if a[i] in d:
				d[a[i]] += 1
			else:
				d[a[i]] = 1
			ans += sorted(d.keys(), key=lambda x: (-d[x], x))[:k]
		return ans


import heapq

class Solution:

	def kTop(self, lst, n, k):
		d = {}
		(heap, ans) = ([], [])
		for i in lst:
			try:
				d[i] += 1
			except:
				d[i] = 1
			for (num, count) in d.items():
				heapq.heappush(heap, (-1 * count, num))
			for j in range(len(heap)):
				if j == k:
					break
				ans.append(heapq.heappop(heap)[1])
		return ans


from collections import defaultdict
import heapq

class Element:

	def __init__(self, val, freq):
		self.val = val
		self.freq = freq

	def __lt__(self, other):
		if self.freq == other.freq:
			self.val > other.val
		return self.freq < other.freq

class Solution:

	def kTop(self, a, n, k):
		min_heap = []
		counter = defaultdict(int)

		def add(num):
			counter[num] += 1
			if (counter[num] - 1, -num) in min_heap:
				min_heap.remove((counter[num] - 1, -num))
				heapq.heapify(min_heap)
			if len(min_heap) > k:
				heapq.heappop(min_heap)
			heapq.heappush(min_heap, (counter[num], -num))

		def k_top():
			return [-num for (freq, num) in heapq.nlargest(k, min_heap)]
		ans = []
		for num in a:
			add(num)
			ans.extend(k_top())
		return ans