215. Kth Largest Element in an Array

from heapq import heappop, heappush
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        hp = []
        res = 0
        n = len(nums)
        target = n-k+1
        for num in nums:
            heappush(hp,-num)
            if len(hp) > target:
                heappop(hp)
        res = heappop(hp)
        return -res

class Solution:
    # time O(N) space O(1) on average  
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # step1: initialize , recalculate k 
        size = len(nums) # arr length 
        k = size - k  # target 
        # step2: set up range   [lo,hi]
        lo,hi = 0,size-1
        while lo < hi:
            # step3:  get partition point pos, change lo,hi based on comparison with pos and k    
            pos = self.partition(nums,lo,hi)
            if pos < k:
                lo = pos+1
            elif pos > k :
                hi = j -1 
            else:# pos == k
                break
        return nums[k]
    #  partition returns a index i , where [lo,i] is less than the pivot, (i,len(arr)-1] is bigger than pivot 
    def partition(self,arr,lo,hi):
        # step1, choose pivot point 
        p = arr[hi]
        # step2, set lo point 
        i = lo 
        for j in range(lo,hi):
            if arr[j] <= p :
                arr[i],arr[j] = arr[j],arr[i]
                i += 1 
        # swap i and hi(pivot point) 
        arr[i],arr[hi] = arr[hi],arr[i]
        return i