Leetcode # 215. Kth Largest Element in an Array

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

Solution

n := len(nums)

Time Complexity: O(n * log(k))
Space Complexity: O(k)
(The input and output generally do not count towards the space complexity.)

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

    def find_insert_i(nums, num):
      left, right = 0, len(nums)
      while left < right:
        mid = (left + right) // 2
        if nums[mid] < num: left = mid + 1 
        else: right = mid
      return left
    
    kth_largest = []
    for num in nums:
      i = find_insert_i(kth_largest, num)
      kth_largest.insert(i, num)
      if len(kth_largest) > k: kth_largest.pop(0)

    return kth_largest[0]

#BinarySearch

Last Updated on 2023/08/16 by A1go