Problem
Approach
| Time Complexity | O(N + K Log N) |
| Auxiliary Space | O(N) |
My Code
Code Answer
Using Priority Queue , Heap
# Python3 code to implement the approach
import heapq
# Function to find the kth smallest array element
def kthSmallest(arr, N, K):
# For finding min element we need (Max heap)priority queue
pq = []
for i in range(K):
# First push first K elements into heap
heapq.heappush(pq, arr[i])
heapq._heapify_max(pq)
# Now check from k to last element
for i in range(K, N):
# If current element is < first that means
# there are other k-1 lesser elements
# are present at bottom thus, pop that element
# and add kth largest element into the heap till curr
# at last all the greater element than kth element will get pop off
# and at the top of heap there will be kth smallest element
if arr[i] < pq[0]:
heapq.heappop(pq)
# Push curr element
heapq.heappush(pq, arr[i])
heapq._heapify_max(pq)
# Return first of element
return pq[0]
# Driver's code:
if __name__ == "__main__":
N = 10
arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]
K = 4
# Function call
print("Kth Smallest Element is:", kthSmallest(arr, N, K))