Kth largest Element

'''
Logic:
Basically we have to find the Kth largest element in array of size n that will be the (n-k)th element if we
sort that array.
so,we will select an element for pivot(last element) and find it's actual position in sorted array.
using partition function and compare that position with k if same then that is our actual element else
we will check,if k is in left of that position,pass the left array in partition else right.
This fails in the sorted long array and gives the O(N*N) as you take pivot as last element and everytime put it into it's posiiton and iterate all elements for each pivot.
'''

def partition(arr,l,r):
    pivot=arr[r]
    k=l
    i=l
    while i<r:
        if arr[i]<arr[r]:
            arr[k],arr[i]=arr[i],arr[k]
            i+=1
            k+=1
        else:
            i+=1
    arr[k],arr[r]=arr[r],arr[k]
    return k

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

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        k=len(nums)-k
        return quick_select(nums,0,len(nums)-1,k)


M-2: Use the Min heap approach. T.C O(Nlog(k))
from heapq import heapify,heappush,heappop
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap=[]
        for i in nums:
            if len(heap)<k:
                heappush(heap,i)
            elif heap[0]<i:
                heappop(heap)
                heappush(heap,i)
        return heap[0]