Given an array, the task is to print K smallest elements from the array but they must be in the same order as they are in a given array.
Example 1:
 
Input : A[] = {1, 2, 2, 3, 1} and K = 2
Output : 1 1
Explanation:
In an array A[] = {1, 2, 2, 3, 1} the smallest
element is 1 and the second smallest element 
is also 1. So, we will return [1, 1] as an 
answer.
Example 2:
Input : A[] = {1, 4, 3, 3, 5, 5} and K = 2
Output : 1 3
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function kSmallestElements() that takes an array (arr), sizeOfArray (n), element (K) and return the array of K smallest element. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ K ≤ N ≤ 10^{6}
1 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

#User function Template for python3

class Solution:
    def kSmallestElements (self, arr, n, k) : 
    #Complete the function




Solutions:
class Solution:

	def kSmallestElements(self, a, n, k):
		d = {}
		for i in range(n):
			d[i] = arr[i]
		result = sorted(d.items(), key=lambda x: x[1])[:k]
		return [item[1] for item in sorted(result)]


class Solution:

	def kSmallestElements(self, arr, n, k):
		cap = sorted(arr)[k - 1]
		output = []
		for item in arr:
			if item <= cap:
				output.append(item)
		i = -1
		while len(output) > k:
			if output[i] == cap:
				output.pop(i)
			else:
				i -= 1
		return output


class Solution:

	def kSmallestElements(self, arr, n, k):
		res = arr[:]
		res.sort()
		freq = {}
		for i in range(k):
			if res[i] not in freq:
				freq[res[i]] = 0
			freq[res[i]] += 1
		ans = []
		for i in arr:
			if i in freq and freq[i] > 0:
				ans.append(i)
				freq[i] -= 1
		return ans


class Solution:

	def kSmallestElements(self, arr, n, k):
		a = [0] * n
		a[:] = arr[:]
		a.sort()
		s = {}
		a = a[0:k]
		for i in a:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		ans = [0] * k
		j = 0
		for i in arr:
			if i in s:
				if s[i] >= 1 and j < k:
					ans[j] = i
					s[i] -= 1
					j += 1
		return ans


class Solution:

	def kSmallestElements(self, arr, n, k):
		dict = {}
		Arr = []
		A = sorted(arr)
		A = A[0:k]
		for i in range(k):
			if A[i] not in dict:
				dict[A[i]] = 1
			else:
				dict[A[i]] += 1
		for i in range(n):
			if arr[i] not in dict:
				continue
			elif dict[arr[i]] >= 1:
				Arr.append(arr[i])
				dict[arr[i]] -= 1
			else:
				continue
		return Arr


class Solution:

	def mergesort(self, arr):
		if len(arr) > 1:
			mid = len(arr) // 2
			L = arr[:mid]
			R = arr[mid:]
			self.mergesort(L)
			self.mergesort(R)
			i = j = k = 0
			while i < len(L) and j < len(R):
				if L[i] < R[j]:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
				k += 1
			while i < len(L):
				arr[k] = L[i]
				k += 1
				i += 1
			while j < len(R):
				arr[k] = R[j]
				k += 1
				j += 1

	def kSmallestElements(self, arr, n, k):
		a = []
		out = []
		sm = []
		border = sorted(arr)[k - 1]
		for i in arr:
			if i <= border:
				sm.append(i)
		cnt = 0
		i = -1
		while len(sm) > k:
			if sm[i] == border:
				sm.pop(i)
			else:
				i -= 1
		return sm


from collections import Counter

class Solution:

	def kSmallestElements(self, arr, n, k):
		s = sorted(arr)[:k]
		x = max(s)
		res = []
		for i in arr:
			if i <= x:
				res.append(i)
		j = -1
		while len(res) > k:
			if res[j] == x:
				res.pop(j)
			else:
				j -= 1
		return res


class Solution:

	def kSmallestElements(self, arr, n, k):
		mini = sorted(arr)[k - 1]
		stack = []
		for item in arr:
			if item <= mini:
				stack.append(item)
		i = -1
		while len(stack) > k:
			if stack[i] == mini:
				stack.pop(i)
			else:
				i -= 1
		return stack


class Solution:

	def kSmallestElements(self, arr, n, k):
		d = {}
		for j in range(n):
			if arr[j] in d:
				d[arr[j]].append(j)
			else:
				d[arr[j]] = [j]
		arr.sort()
		a = arr[:k]
		r = [-1] * n
		for j in a:
			r[d[j][0]] = j
			d[j].remove(d[j][0])
		r = [j for j in r if j != -1]
		return r


class Solution:

	def kSmallestElements(self, arr, n, k):
		frq = dict()
		temp = sorted(arr)
		sum = 0
		for i in range(0, n):
			if sum == k:
				break
			num = temp[i]
			if num in frq:
				frq[num] += 1
			else:
				frq[num] = 1
			sum = sum + 1
		ans = list()
		for element in arr:
			if element in frq:
				if frq[element] > 0:
					ans.append(element)
				frq[element] -= 1
		return ans


class Solution:

	def kSmallestElements(self, arr, n, k):
		freq = dict()
		temp = sorted(arr)
		tot = 0
		for i in range(n):
			if tot == k:
				break
			num = temp[i]
			if num in freq:
				freq[num] += 1
			else:
				freq[num] = 1
			tot += 1
		res = []
		for element in arr:
			if element in freq:
				if freq[element] > 0:
					res.append(element)
				freq[element] -= 1
		return res


from heapq import *

class Solution:

	def kSmallestElements(self, arr, n, k):
		dict1 = {}
		ans = []
		res = []
		arr1 = []
		arr1 = sorted(arr)
		for i in range(0, k):
			ans.append(arr1[i])
		for ele in ans:
			if ele in dict1:
				dict1[ele] += 1
			else:
				dict1[ele] = 1
		for ele in arr:
			if ele in dict1:
				res.append(ele)
				dict1[ele] -= 1
				if dict1[ele] == 0:
					del dict1[ele]
		return res
		return res


class Solution:

	def kSmallestElements(self, arr, n, k):
		d = {}
		ls = []
		tem = k
		sar = sorted(arr)
		for x in sar:
			if tem == 0:
				break
			if x not in d:
				d[x] = 1
				tem -= 1
			else:
				d[x] += 1
				tem -= 1
		i = 0
		while k > 0:
			try:
				if arr[i] in d:
					if d[arr[i]] == 0:
						del d[arr[i]]
					d[arr[i]] -= 1
					ls.append(arr[i])
					i += 1
					k -= 1
				else:
					i += 1
			except:
				i += 1
		return ls


class Solution:

	def kSmallestElements(self, arr, n, k):
		a = arr[:]
		a.sort()
		a = a[:k]
		res = []
		i = 0
		for elem in arr:
			if i >= k:
				break
			pivot = a[-1]
			if elem <= pivot:
				res.append(elem)
				if elem == pivot:
					a.pop()
				i += 1
		return res


class Solution:

	def kSmallestElements(self, arr, n, k):
		d = {}
		for i in range(n):
			d[i] = [arr[i], i]
		m = sorted(d.values())
		l = []
		i = 0
		while len(l) < k:
			l.append(m[i])
			i += 1
		l.sort(key=lambda x: x[-1])
		l1 = []
		for i in l:
			l1.append(i[0])
		return l1


class Solution:

	def kSmallestElements(self, arr, n, k):
		l = []
		s = {}
		j = 0
		a = sorted(arr)
		while j < k:
			if a[j] not in s:
				s[a[j]] = 1
			else:
				s[a[j]] = s[a[j]] + 1
			j += 1
		for i in arr:
			if len(l) == k:
				return l
			if i in s and s[i]:
				l.append(i)
				s[i] -= 1
		return l


class Solution:

	def kSmallestElements(self, arr, n, k):
		new_arr = sorted(arr)
		dict1 = {}
		for i in range(k):
			dict1[new_arr[i]] = dict1.get(new_arr[i], 0) + 1
		result = []
		for element in arr:
			if element in dict1:
				if dict1[element] > 0:
					result.append(element)
				dict1[element] -= 1
		return result


class Solution:

	def kSmallestElements(self, arr, n, k):
		mp = {}
		tmp = sorted(arr)
		s = 0
		for i in range(0, n):
			if s == k:
				break
			num = tmp[i]
			if num in mp:
				mp[num] += 1
			else:
				mp[num] = 1
			s += 1
		ans = []
		for ele in arr:
			if ele in mp:
				if mp[ele] > 0:
					ans.append(ele)
				mp[ele] -= 1
		return ans


class Solution:

	def kSmallestElements(self, arr, n, k):
		a = arr[:]
		a.sort()
		a = a[:k]
		res = []
		l = 0
		j = 0
		while l < k:
			pivot = a[-1]
			if arr[j] <= pivot:
				res.append(arr[j])
				if arr[j] == pivot:
					a.pop()
				l += 1
			j += 1
		return res


class Solution:

	def kSmallestElements(self, arr, n, k):
		a = []
		for i in range(n):
			a.append([arr[i], i])
		a.sort(key=lambda k: k[0])
		b = a[:k]
		b.sort(key=lambda k: k[1])
		res = []
		for i in b:
			res.append(i[0])
		return res


class Solution:

	def kSmallestElements(self, arr, n, k):
		orderarr = []
		for i in range(n):
			orderarr.append([arr[i], i])
		orderarr.sort(key=lambda x: x[0])
		newarr = orderarr[:k]
		newarr.sort(key=lambda x: x[1])
		res = []
		for ele in newarr:
			res.append(ele[0])
		return res


class Solution:

	def kSmallestElements(self, arr, n, k):
		brr = sorted(arr)[:k]
		d = {}
		for i in brr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		maxl = brr[-1]
		ans = []
		for i in arr:
			if i <= maxl and d[i] > 0:
				ans.append(i)
				d[i] -= 1
		return ans


class Solution:

	def kSmallestElements(self, arr, n, k):
		x = sorted(arr)[:k]
		d1 = {}
		for i in x:
			if i in d1:
				d1[i] += 1
			else:
				d1[i] = 1
		ans = []
		d2 = {}
		for i in arr:
			if i in d1:
				if i not in d2:
					ans.append(i)
					d2[i] = 1
				elif d2[i] < d1[i]:
					ans.append(i)
					d2[i] += 1
		return ans


class Solution:

	def kSmallestElements(self, arr, n, k):
		a = arr.copy()
		arr.sort()
		d = {}
		res = []
		for i in arr[:k]:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in a:
			if i in d and d[i] > 0:
				d[i] -= 1
				res.append(i)
		return res


class Solution:

	def kSmallestElements(self, arr, n, k):
		temp = []
		d = {}
		c = sorted(arr)
		for i in range(k):
			if c[i] in d:
				d[c[i]] += 1
			else:
				d[c[i]] = 1
		for j in arr:
			if j in d:
				if d[j] > 0:
					temp.append(j)
				d[j] -= 1
		return temp


class Solution:

	def kSmallestElements(self, arr, n, k):
		z = sorted(arr)
		t = {}
		for i in range(k):
			if z[i] not in t:
				t[z[i]] = 1
			else:
				t[z[i]] += 1
		s = []
		for i in arr:
			if i in t and t[i] > 0:
				s.append(i)
				t[i] -= 1
		return s


class Solution:

	def kSmallestElements(self, arr, n, k):
		brr = sorted(arr)[:k]
		d = {}
		for i in brr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		maxl = brr[-1]
		ans = []
		for i in arr:
			if i <= maxl and d[i] > 0:
				ans.append(i)
				d[i] -= 1
		return ans
for _ in range(0, int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	res = Solution().kSmallestElements(arr, n, K)
	print(*res)


class Solution:

	def kSmallestElements(self, arr, n, k):
		b = []
		for i in arr:
			b.append(i)
		b.sort()
		b = b[:k]
		s = {}
		for i in b:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		c = []
		for i in arr:
			if i in s and s[i] >= 1:
				c.append(i)
				s[i] -= 1
		return c
for _ in range(0, int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().strip().split()))
	res = Solution().kSmallestElements(arr, n, K)
	print(*res)


import heapq as HQ

class Solution:

	def kSmallestElements(self, a, n, k):
		a = list(enumerate(a))
		a.sort(key=lambda x: x[1])
		a = a[:k]
		HQ.heapify(a)
		t = []
		for i in range(k):
			t.append(HQ.heappop(a)[1])
		return t


class Solution:

	def kSmallestElements(self, arr, n, k):
		sarr = sorted(arr)
		d = {}
		ans = []
		for i in range(0, k):
			d[sarr[i]] = d.get(sarr[i], 0) + 1
		for i in range(n):
			if arr[i] in d:
				d[arr[i]] -= 1
				if d[arr[i]] == 0:
					del d[arr[i]]
				ans.append(arr[i])
		return ans


class Solution:

	def binary_search(arr, low, high, ele):
		while low < high:
			mid = (low + high) // 2
			if arr[mid] == ele:
				return mid
			elif arr[mid] > ele:
				high = mid
			else:
				low = mid + 1
		return -1

	def kSmallestElements(self, arr, n, k):
		new_arr = sorted(arr)
		ans = new_arr[:k]
		final_arr = []
		for i in arr:
			if Solution.binary_search(ans, low=0, high=len(ans), ele=i) > -1:
				final_arr.append(i)
				ans.remove(i)
			if len(final_arr) == k:
				return final_arr


class Solution:

	def kSmallestElements(self, arr, n, k):
		from collections import OrderedDict
		counter = OrderedDict()
		arr2 = arr[:]
		arr2.sort()
		res = []
		for i in range(0, k):
			counter.setdefault(arr2[i], 0)
			counter[arr2[i]] += 1
		i = 0
		c = k
		while i < n and c > 0:
			if arr[i] in counter:
				if counter[arr[i]] > 0:
					res.append(arr[i])
					counter[arr[i]] -= 1
					c -= 1
			i += 1
		return res