0215.Kth Largest Element in an Array

• Link: 215. Kth Largest Element in an Array - Medium
• Track: NeetCode150

Question

Restate the problem

• Given an integer array nums and an integer k
• Return the kth largest element in the array
• Note:
  • it is the kth largest in sorted order
  • not the kth distinct element

Edge Case

• k = len(nums) → return the smallest element

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Heap	$O(nlogn)$	$O(n)$

Method 1

Key idea:
Build a max heap, then pop k times. The last popped value is the kth largest.
先用 heap 建一个最大堆，然后弹出 k 次，最后一次弹出的值就是第 k 大。

Approach

• Python heapq is a min heap
• To simulate a max heap, push -num into the heap
• Pop from the heap k times
• The last popped value is the kth largest element

Complexity

• Time Complexity: $O(nlogn)$
• Space Complexity: $O(n)$

Code

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        max_heap = []
 
        for num in nums:
            heapq.heappush(max_heap, -num)
        
        while k and max_heap:
            val = heapq.heappop(max_heap)
            k -= 1
        
        return -val

---

Mistake

• Forget to convert back at the end: return -val