Given an array arr[] and an integer K where K is smaller than size of array, the task is to find the K^{th} smallest element in the given array. It is given that all array elements are distinct.
Note :-  l and r denotes the starting and ending index of the array.
Example 1:
Input:
N = 6
arr[] = 7 10 4 3 20 15
K = 3
Output : 7
Explanation :
3rd smallest element in the given 
array is 7.
Example 2:
Input:
N = 5
arr[] = 7 10 4 20 15
K = 4
Output : 15
Explanation :
4th smallest element in the given 
array is 15.
Your Task:
You don't have to read input or print anything. Your task is to complete the function kthSmallest() which takes the array arr[], integers l and r denoting the starting and ending index of the array and an integer K as input and returns the K^{th} smallest element. 
 
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(log(n))
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{5}
1 <= K <= N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def kthSmallest(self,arr, l, r, k):

        '''

        arr : given array

        l : starting index of the array i.e 0

        r : ending index of the array i.e size-1

        k : find kth smallest element and return using this function

        '''

Solutions:
class Solution:

	def kthSmallest(self, arr, l, r, k):
		arr.sort()
		return arr[k - 1]


class Solution:

	def kthSmallest(self, arr, l, r, k):
		arr = sorted(arr)
		return arr[k - 1]


import heapq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		heapq.heapify(arr)
		return heapq.nsmallest(k, arr)[-1]


class Solution:

	def partionAlgo(self, arr, pivot, low, right):
		i = low
		j = low
		while i <= right:
			if arr[i] > pivot:
				i += 1
			else:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
				j += 1
		return arr.index(pivot)

	def kthSmallestHelper(self, arr, k, left, right):
		if k > len(arr):
			return -1
		if left == right:
			return arr[left]
		pivot_index = self.partionAlgo(arr, arr[right], left, right)
		if pivot_index == k - 1:
			return arr[pivot_index]
		elif pivot_index > k - 1:
			return self.kthSmallestHelper(arr, k, left, pivot_index - 1)
		else:
			return self.kthSmallestHelper(arr, k, pivot_index + 1, right)

	def kthSmallest(self, arr, l, r, k):
		return self.kthSmallestHelper(arr, k, l, r)


class Solution:

	def kthSmallest(self, arr, l, r, k):
		if k > 0 and k <= r - l + 1:
			pos = partition(arr, l, r)
			if pos - l == k - 1:
				return arr[pos]
			elif pos - l > k - 1:
				return self.kthSmallest(arr, l, pos - 1, k)
			else:
				return self.kthSmallest(arr, pos + 1, r, k - pos + l - 1)
		return None

def partition(arr, l, r):
	x = arr[r]
	i = l
	for j in range(l, r):
		if arr[j] <= x:
			(arr[i], arr[j]) = (arr[j], arr[i])
			i += 1
	(arr[i], arr[r]) = (arr[r], arr[i])
	return i


import heapq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		heapq.heapify(arr)
		ans = 0
		for i in range(k):
			ans = heapq.heappop(arr)
		return ans


class Solution:

	def kthSmallest(self, arr, l, r, k):
		arr.sort()
		count = 0
		for i in range(len(arr)):
			count += 1
			if count == k:
				return arr[i]


class Solution:

	def kthSmallest(self, arr, l, r, k):
		return self.kthSmallestUtil(arr, l, r, k - 1)

	def partition(self, arr, low, high):
		pivot_index = random.randint(low, high)
		(arr[pivot_index], arr[high]) = (arr[high], arr[pivot_index])
		i = low
		for j in range(low, high):
			if arr[j] < arr[high]:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
		(arr[i], arr[high]) = (arr[high], arr[i])
		return i

	def kthSmallestUtil(self, arr, l, r, k):
		if l == r:
			return arr[l]
		pivot_index = self.partition(arr, l, r)
		if k == pivot_index:
			return arr[k]
		elif k < pivot_index:
			return self.kthSmallestUtil(arr, l, pivot_index - 1, k)
		else:
			return self.kthSmallestUtil(arr, pivot_index + 1, r, k)


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def swap(self, arr, a, b):
		temp = arr[a]
		arr[a] = arr[b]
		arr[b] = temp

	def randomPartition(self, arr, l, r):
		n = r - l + 1
		pivot = int(random.random() % n)
		self.swap(arr, l + pivot, r)
		return self.partition(arr, l, r)

	def kthSmallest(self, arr, l, r, k):
		if k > 0 and k <= r - l + 1:
			pos = self.randomPartition(arr, l, r)
			if pos - l == k - 1:
				return arr[pos]
			if pos - l > k - 1:
				return self.kthSmallest(arr, l, pos - 1, k)
			return self.kthSmallest(arr, pos + 1, r, k - pos + l - 1)
		return 999999999999

	def partition(self, arr, l, r):
		x = arr[r]
		i = l
		for j in range(l, r):
			if arr[j] <= x:
				self.swap(arr, i, j)
				i += 1
		self.swap(arr, i, r)
		return i


class Solution:

	def kthSmallest(self, arr, l, r, k):
		d = {}
		for ele in arr:
			d[ele] = d.get(ele, 0) + 1
		n = 0
		for ele in sorted(d.keys()):
			n += d[ele]
			if n == k:
				return ele


class Solution:

	def kthSmallest(self, arr, l, r, k):
		counting = [0] * (10 ** 5 + 1)
		for i in arr:
			counting[i] += 1
		count = 0
		for i in range(10 ** 5 + 1):
			count += counting[i]
			if count >= k:
				return i


from heapq import heappop, heappush

class Solution:

	def kthSmallest(self, arr, l, r, k):
		maxHeap = []
		for i in range(0, len(arr)):
			heappush(maxHeap, arr[i])
		for j in range(0, k):
			element = heappop(maxHeap)
		return element


import heapq as hq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		hq.heapify(arr)
		res = 0
		while k > 0:
			res = hq.heappop(arr)
			k -= 1
		return res


import numpy as np

class Solution:

	def kthSmallest(self, arr, l, r, k):
		arr = np.array(arr)
		arr = arr[l:r + 1]
		arr.sort()
		return arr[k - 1]


class Solution:

	def partition(self, arr, l, r):
		x = arr[r]
		i = l
		for j in range(l, r):
			if arr[j] <= x:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
		(arr[i], arr[r]) = (arr[r], arr[i])
		return i

	def kthSmallest(self, arr, l, r, k):
		if k > 0 and k <= r - l + 1:
			index = self.partition(arr, l, r)
			if index - l == k - 1:
				return arr[index]
			if index - l > k - 1:
				return self.kthSmallest(arr, l, index - 1, k)
			else:
				return self.kthSmallest(arr, index + 1, r, k - index + l - 1)
		return -1


import heapq as h

class Solution:

	def kthSmallest(self, arr, l, r, k):
		h.heapify(arr)
		for i in range(k):
			res = h.heappop(arr)
		return res


import heapq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		s = []
		for i in arr:
			heapq.heappush(s, i)
		while k > 0:
			z = heapq.heappop(s)
			k = k - 1
		return z


import heapq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		heapq.heapify(arr)
		st = []
		for i in range(k):
			st.append(heapq.heappop(arr))
		return st[-1]


class Solution:

	def kthSmallest(self, arr, l, r, k):
		p = set(arr)
		q = sorted(p)
		return q[k - 1]


import heapq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		maxheap = []
		for i in range(0, len(arr)):
			heapq.heappush(maxheap, -arr[i])
		while len(maxheap) > k:
			-heapq.heappop(maxheap)
		return -maxheap[0]


class Solution:

	def kthSmallest(self, arr, l, r, k):
		l = arr[0]
		arr.reverse()
		r = arr[0]
		arr.sort()
		asf = arr[k - 1]
		return asf


class Solution:

	def kthSmallest(self, arr, l, r, k):

		def count_smaller(mid_el, arr):
			count_sm = 0
			for i in arr:
				if i < mid_el:
					count_sm += 1
			return count_sm
		l = min(arr)
		h = max(arr)
		ans = 0
		while l <= h:
			mid = l + (h - l) // 2
			if count_smaller(mid, arr) >= k - 1:
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		temp = ans
		diff = abs(ans - max(arr))
		for el in arr:
			temp_diff = abs(ans - el)
			if el == ans:
				return ans
			elif ans < el and diff >= temp_diff:
				temp = el
				diff = temp_diff
		return temp


class Solution:

	def kthSmallest(self, arr, l, r, k):
		l = min(arr)
		h = max(arr)
		ans = -1
		while l <= h:
			mid = l + (h - l) // 2
			csm = self.countSmaller(arr, mid)
			if csm >= k - 1:
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		if self.exists(arr, ans):
			return ans
		else:
			return self.nextMax(arr, ans)

	def countSmaller(self, arr, target):
		csm = 0
		for num in arr:
			if num < target:
				csm += 1
		return csm

	def exists(self, arr, target):
		for num in arr:
			if num == target:
				return True
		return False

	def nextMax(self, arr, target):
		maxDiff = abs(target - max(arr))
		nextMax = max(arr)
		for num in arr:
			if abs(num - target) < maxDiff and num > target:
				nextMax = num
				maxDiff = abs(num - target)
		return nextMax


class Solution:

	def kthSmallest(self, arr, l, r, k):
		if l == 0 and r == len(arr) - 1:
			k -= 1
		if l == r:
			return arr[k]
		else:
			i = l
			ele = arr[l]
			for j in range(l + 1, r + 1):
				if arr[j] <= ele:
					i += 1
					(arr[i], arr[j]) = (arr[j], arr[i])
			(arr[l], arr[i]) = (arr[i], arr[l])
		pivot = i
		if pivot == k:
			return arr[k]
		elif pivot > k:
			return self.kthSmallest(arr, l, pivot - 1, k)
		else:
			return self.kthSmallest(arr, pivot + 1, r, k)


class Solution:

	def kthSmallest(self, arr, l, r, k):

		def fun(arr, l, r, k):
			if l == r:
				return arr[k]
			else:
				i = l
				ele = arr[l]
				for j in range(l + 1, r + 1):
					if arr[j] <= ele:
						i += 1
						(arr[i], arr[j]) = (arr[j], arr[i])
				(arr[l], arr[i]) = (arr[i], arr[l])
			pivot = i
			if pivot == k:
				return arr[k]
			elif pivot > k:
				return fun(arr, l, pivot - 1, k)
			else:
				return fun(arr, pivot + 1, r, k)
		return fun(arr, l, r, k - 1)


import heapq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		h = []
		for i in range(k):
			heapq.heappush(h, -arr[i])
		for i in range(k, r + 1):
			if -h[0] > arr[i]:
				heapq.heappop(h)
				heapq.heappush(h, -arr[i])
		return -h[0]


import heapq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		count = 1
		heapq.heapify(arr)
		while count < k:
			heapq.heappop(arr)
			count += 1
		return heapq.heappop(arr)


class Solution:

	def kthSmallest(self, arr, l, r, k):

		def partition(arr, l, r):
			pivot = arr[r]
			i = l - 1
			for j in range(l, r):
				if arr[j] <= pivot:
					i += 1
					(arr[i], arr[j]) = (arr[j], arr[i])
			(arr[i + 1], arr[r]) = (arr[r], arr[i + 1])
			return i + 1

		def quickSelect(arr, l, r, k):
			if l <= r:
				pivot_index = partition(arr, l, r)
				if pivot_index == k - 1:
					return arr[pivot_index]
				elif pivot_index > k - 1:
					return quickSelect(arr, l, pivot_index - 1, k)
				else:
					return quickSelect(arr, pivot_index + 1, r, k)
		return quickSelect(arr, l, r, k)


import heapq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		pq = []
		n = len(arr)
		for i in range(n):
			heapq.heappush(pq, -1 * arr[i])
			if i >= k:
				heapq.heappop(pq)
		return -1 * pq[0]


from heapq import heappop, heappush

class Solution:

	def kthSmallest(self, arr, l, r, k):
		min_heap = []
		for ele in arr:
			heappush(min_heap, ele)
		while k > 1:
			heappop(min_heap)
			k -= 1
		return min_heap[0]