Kth Largest Element in an Array

Given an integer array and an integer k, return the kth largest element in sorted order. This is the kth largest by value, not the kth distinct value, so duplicates count. You are not required to sort the whole array.

Example#

For nums = [3, 2, 1, 5, 6, 4] and k = 2, the sorted order descending is 6, 5, 4, 3, 2, 1, so the 2nd largest is 5. For nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4, the answer is 4.

Brute force note#

Sorting the array and indexing the kth largest is O(n log n) and simple, but it does more work than needed: you sort every element when you only care about the top k.

Optimal approach#

Keep a min-heap of size k. Push elements one at a time; whenever the heap grows past k, pop the smallest. After processing every element, the heap holds exactly the k largest values, and its smallest (the root) is the kth largest overall. Python’s heapq is a min-heap, so the root is heap[0].

 1import heapq
 2
 3
 4def find_kth_largest(nums, k):
 5    heap = []
 6    for x in nums:
 7        heapq.heappush(heap, x)
 8        if len(heap) > k:
 9            heapq.heappop(heap)
10    return heap[0]
11
12
13print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))              # 5
14print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))     # 4

Complexity#

Time is O(n log k): each of the n elements triggers a heap operation costing O(log k). Space is O(k) for the heap. This beats a full sort when k is much smaller than n. Quickselect gives O(n) average time if you need it.

This is the definitive top K with heaps problem. Reinforce the fixed-size heap trick there, then continue through the 60-day curriculum.