215. Kth Largest Element in an Array

Medium

Problem:

Extract the kth largest element from an unsorted array. (Can you solve it without sorting?)

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

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

Solution:

Relevant problem ⬇️

347. Top K Frequent Elements

heapq

The Python heapq module only supports a min-heap. Thus, by storing numbers as negatives and then extracting the smallest numbers and converting their signs, we can implement it to function like a max-heap.

Reference to heapq: Heap queue (or heapq) in Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = list()
        for n in nums:
            heapq.heappush(heap, -n)
        
        for _ in range(k):
            heapq.heappop(heap)
        
        return -heapq.heappop(heap)

heapq.heapify

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        
        for _ in range(len(nums) - k):
            heapq.heappop(nums)
        
        return heapq.heappop(nums)

heapq.nlargest

The k-th largest values are returned in a list, starting from the largest value.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

Sorting

When additions and deletions are frequent, heap sorting using heapq is useful. However, when the input is fixed as in this case, just sorting once is sufficient.

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

By using sorted() to sort in descending order, a more intuitive solution is also possible.

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

Summary:

All methods have little difference in execution speed, but the 'sorting' method is the fastest. Python's sorting function uses Timsort, which is very intricately implemented in C. In most cases, using Python's built-in sorting function provides the best performance.