Kth Largest Element In An Array

---

Intuition

• This problem could be solved using Quickselect which would make the problem considerably harder.

Complexity

Runtime

• $O(NlogN)$ with sorting
• $O(N+klogN)$, where k is the number of elements popped from the heap, and k is the number of elements popped from the heap (passed in)

Space

$O(N)$ for the heap (could be done in place though as well for $O(1)$)

Code

Heap

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = [-num for num in nums]
        heapify(heap)
 
        num = -1
        for _ in range(k - 1, -1, -1):
            num = heappop(heap)
        return -num

Sorted

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

Cards

START Basic Front: Kth Largest Element In An Array Back: Heappop the negative values END

---

References

• Kth Largest Element In An Array