Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:


Input: [3,2,1,5,6,4] and k = 2
Output: 5


Example 2:


Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

Difficulty: interview

Starter code:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        

Solutions:
class Solution:
     def findKthLargest(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         nums = sorted(nums, reverse=True)
         return nums[k - 1]

class Solution:
     def findKthLargest(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         nums.sort()
         return nums[len(nums) - k]

class Solution:
     def findKthLargest(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         heap = []
         for num in nums:
             heapq.heappush(heap,num)
         for _ in range(len(nums)-k):
             heapq.heappop(heap)
         return heapq.heappop(heap)


class Solution:
     def findKthLargest(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         if not nums: return -1;
         pq = [];
 
         for num in nums:
             if len(pq) < k:
                 heapq.heappush(pq,num);
             else:
                 popped = heapq.heappop(pq);
                 if popped < num:
                     heapq.heappush(pq, num);
                 else:
                     heapq.heappush(pq, popped);
 
         return heapq.heappop(pq);        

class Solution:
     def findKthLargest(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         
         def partition(nums, ind, i, j):
             
             big, scan = i, i
             
             nums[ind], nums[j] = nums[j], nums[ind]
             
             while scan < j:
                 if nums[scan] > nums[j]:
                     nums[big], nums[scan] = nums[scan], nums[big]
                     big += 1
                     
                 scan += 1
                     
             nums[j], nums[big] = nums[big], nums[j]
             # print(nums)
             # print(big)
             return big
             
         
         # 12 53 - 1 09
         
         
         i, j = 0, len(nums)-1
         while i <= j:
             ind = random.randint(i, j)
             new_ind = partition(nums, ind, i, j)
             if new_ind == k-1: 
                 return nums[new_ind]
             elif new_ind < k-1: 
                 i = new_ind + 1
             else:
                 j = new_ind - 1
                 
         return -1 
         
         
             


class Solution:
     def findKthLargest(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         sor = sorted(nums)
         lenn = len(nums)
         return sor[lenn-1-(k-1)]

class Solution:
     def findKthLargest(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         return sorted(nums)[len(nums) - k]

class Solution:
     def swap(self, A, i, j ):
         if A[i] != A[j]:
             A[i],A[j] = A[j],A[i]
     def partition(self, A, p, r):
         self.swap(A, r, random.randint(p, r))
         x = A[r]
         j = p - 1
         for i in range(p, r):
             if A[i] <= x:
                 j += 1
                 self.swap(A, i, j)
         j += 1
         self.swap(A, r, j)
         return j
     def findElement(self, A, k):
         low, high = 0, len(A) - 1
         while low < high:
             i = self.partition(A, low, high)
             if i > k:
                 high = i - 1
             elif i < k :
                 low = i + 1
             else:
                 return A[k]
         return A[k]
     
     def findKthLargest(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         return self.findElement(nums, len(nums) - k)