Given an integer array nums and an integer k, return the kth largest element in sorted order — not the kth distinct value, so duplicates count separately.
Example
Input nums = [3,2,1,5,6,4], k = 2
Output 5
Key Pointers
A full sort answers this in O(n log n), but a min-heap capped at size k gets it down to O(n log k).
The heap only ever needs to hold the current top-k candidates — anything smaller than the heap's minimum can't be the answer, so evict it immediately.
Once every element is processed, the heap's root is exactly the kth largest — no extra pass needed.
Step-by-Step Analysis
Create an empty min-heap.
For each number in nums, push it onto the heap.
If the heap's size exceeds k, pop the smallest element.
After the array is fully processed, return the heap's root.
Complexity
Time: O(n log k) — Space: O(k)
Code
import heapq
def findKthLargest(nums: list[int], k: int) -> int:
heap = []
for n in nums:
heapq.heappush(heap, n)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
Code Explanation
How the solution above works, piece by piece.
Keep a min-heap of the k largest values seen so far.
Push each number; if the heap has more than k items, pop the smallest.
What's left are the k largest numbers, and the smallest of them, heap[0], is the k-th largest.
O(n log k) time and O(k) space, better than sorting (O(n log n)) when k is small.
Visual Walkthrough
Running it on nums = [3, 2, 1, 5, 6, 4], k = 2:
With k = 2 the heap never holds more than two numbers. After the last push it holds 5 and 6, so the 2nd largest is 5.