Kth Largest Element in an Array (Leetcode 215)

Problem Link: https://leetcode.com/problems/kth-largest-element-in-an-array/

Using Heap

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        # Creating maxheap and removing k-1 elements from it.
        # After this, the top element will be the kth largest
        pq=[]
        heapq.heapify(pq)
        for i in nums:
            heapq.heappush(pq,-i)
        
        for i in range(k-1):
            heapq.heappop(pq)
        
        ans=-1*(heapq.heappop(pq))
        return ans

Using Quick Select

Worst Case: O(N^2) and Average Case: O(N)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Watch neetcode's video if you don't understand
        k=len(nums)-k
        
        def quickselect(nums,k,left,right):
            
            ptr=left
            pivot=nums[right]
            
            for i in range(left,right):
                if(nums[i]<=pivot):
                    nums[i],nums[ptr]=nums[ptr],nums[i]
                    ptr+=1
            
            nums[ptr],nums[right]=nums[right],nums[ptr]
            if(ptr>k):
                return quickselect(nums,k,left,ptr-1)
            elif(ptr<k):
                return quickselect(nums,k,ptr+1,right)
            else:
                return nums[ptr]
        
        return quickselect(nums,k,0,len(nums)-1)