Kth Largest Element in an Array
A size-k min-heap keeps exactly the k largest seen so far.
Heap Trace
Problem
Given an integer array and an integer k, determine which value would appear in position k when the array is ordered from largest to smallest. Return that value without needing to produce the entire sorted array. Duplicate values count as separate elements.
Examples
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
The Goal
Return the number at position k when nums is sorted from largest to smallest. Duplicates count separately.
For nums = [3, 2, 1, 5, 6, 4] and k = 2, that order is 6, 5, 4, 3, 2, 1, so the answer is 5.
You don't need the whole order, only the k largest numbers and the smallest of them.
The k-th largest
The k-th largest is the smallest of the k largest numbers.
Keep the k largest, and read off their smallest.
Key Idea: A Min-Heap of Size k
A min-heap keeps its smallest number at the root.
Push each number. When the heap holds k + 1, pop the root: it's the smallest of them, so it isn't among the k largest. After every number, the heap holds the k largest so far, with the k-th largest at the root.
After each number, it holds the k largest so far.
After 3, 2 and 1: 2 and 3.
The Algorithm
import heapq
def find_kth_largest(nums, k):
if k > len(nums):
return None
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]LeetCode promises k is at most len(nums). The first check returns None when it isn't, since then there is no k-th largest.
heapq keeps a min-heap in a plain list. heap[0] is the smallest number, but the rest of the list isn't sorted.
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Sort the array | O(n log n) | O(1) to O(n) | Orders numbers you never need |
| Min-heap of size k | O(n log k) | O(k) | Works on a stream too |
| Quickselect | O(n) on average | O(1) extra | O(n^2) on bad pivots |
Walkthrough
Run it on [3, 2, 1, 5, 6, 4] with k = 2.
3 and 2 fill the heap: [2, 3]. Pushing 1 gives [1, 3, 2], three numbers, so the root 1 pops. 5 and 6 each push out the root: 2, then 3. Pushing 4 gives [4, 6, 5], and 4 pops right back out.
The heap ends as [5, 6], and its root, 5, is the answer.
Checkpoint · predict the next step
Step 6 of 18 on the stage: Read 1.
heap = [2, 3] · k 2 · size 2
Pitfalls
- Use a min-heap. Python's
heapqis one. - Pop only when the heap holds more than
k. Popping atkkeepsk - 1numbers. - Duplicates count. For
[3, 2, 3, 1, 2, 4, 5, 5, 6]andk = 4, the answer is 4. - When
kis the length, nothing pops, and the root is the smallest number. - Read
heap[0]only after every number is in.
With k = 2, why is the root the second largest at the end?
Complexity
The heap never holds more than k + 1 numbers, so each push and pop costs O(log k). With one push and at most one pop per number, time is O(n log k) and extra space is O(k).
Sorting costs O(n log n). Quickselect averages O(n), but bad pivots give O(n²).
A heap of size k
- Push each numberAt most k + 1 in the heap.O(n log k)
- Pop past kAt most one per push.O(n log k)
- The heapThe k largest so far.O(k)
A small heap instead of a full sort.
In short
Push elements into a min-heap; once it exceeds size k, pop the smallest. After the pass, the heap's root is the kth largest. Quickselect gives an average O(n) alternative by partitioning around a pivot without fully sorting.
Common mistake
Fully sorting the array (O(n log n)) when a k-sized heap or quickselect is faster.