Method 1:
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
#Maximum Heap:
#TC: O(n + k log n)
#SC: O(n)
n = len(nums)
Heap = [-ele for ele in nums]
heapq.heapify(Heap)
print(Heap)
for _ in range(k-1):
heapq.heappop(Heap)
return -Heap[0]
Method 2:
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
#Minimum Heap
#TC: O(k+(n-k)*log k)
#SC: O(k)
Heap = nums[:k]
heapq.heapify(Heap)
for ele in nums[k:]:
if ele > Heap[0]:
heapq.heappop(Heap)
heapq.heappush(Heap, ele)
return Heap[0]
Method 3
Quickselect. The idea/algorithm is from
https://www.youtube.com/results?search_query=leetcode+215
This is a recursive version
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
#TC: O(n) T(n) = T(n/2) + O(n)
# = O(n) + O(n/2) + O(n/4) + ... < O(2*n) = O(n)
# Max: O(n^2)
#SC: O(n)
def quickselect(Nums, K):
N = len(Nums)
if N == 1:
return Nums[0]
pivot = Nums[-1]
slow = -1
fast = 0
while(fast < N-1):
if Nums[fast] > pivot:
fast += 1
else:
tmp = Nums[fast]
slow += 1
Nums[fast] = Nums[slow]
Nums[slow] = tmp
fast += 1
slow += 1
Nums[-1] = Nums[slow]
Nums[slow] = pivot
if slow == K-1:
return Nums[slow]
elif slow > K-1:
return quickselect(Nums[:slow], K)
else:
return quickselect(Nums[slow+1:], K-(slow+1))
return quickselect(nums, len(nums) + 1 - k)
Method 4:
Quickselect, iterative version
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
#TC: O(n) T(n) = T(n/2) + O(n)
# = O(n) + O(n/2) + O(n/4) + ... < O(2*n) = O(n)
# Max: O(n^2)
#SC: O(1)
def partition(left, right):
pivot = nums[right]
slow = left - 1
fast = left
while(fast < right):
if nums[fast] >= pivot:
fast += 1
else:
slow += 1
tmp = nums[slow]
nums[slow] = nums[fast]
nums[fast] = tmp
fast += 1
slow += 1
nums[right] = nums[slow]
nums[slow] = pivot
return slow
n = len(nums)
left = 0
right = n - 1
target = n+1-k
while(left <= right):
Idx = partition(left, right)
if Idx+1 == target:
return nums[Idx]
elif Idx+1 > target:
right = Idx - 1
else:
left = Idx + 1
return nums[left]