Kth Smallest element

//Method 1
"""
Time Complexity: O(n log k)
Auxiliary Space: O(k)

We maintain a max-heap of size k (implemented using negatives in Python).
The heap always stores the k smallest elements seen so far, and the top
represents the largest among them, i.e., the kth smallest element.
"""
import heapq
class Solution:
    def kthSmallest(self, arr, k):
        # max-heap of size k using negatives
        heap = [-x for x in arr[:k]]
        heapq.heapify(heap)

        for x in arr[k:]:
            if x < -heap[0]:
                heapq.heapreplace(heap, -x)  # pop + push in one step

        return -heap[0]

#Method 2
#Quick select
def partition(arr,l,r):
    pivot=arr[r]
    k=l
    i,j=l,r
    for i in range(l,r):
        if arr[i]<=pivot:
            arr[i],arr[k]=arr[k],arr[i]
            k+=1
    arr[k],arr[r]=arr[r],arr[k]
    return k

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

class Solution:
    def kthSmallest(self, arr, k):
        return fun(arr,0,len(arr)-1,k-1)