Kth Largest Element in an Array
Kth Largest Element in an Array is LeetCode 215 (Medium). Given an integer array nums and an integer k, return the k-th largest element: the value at position k if nums were sorted from largest to smallest.
- Repeated values each count. It is the k-th largest in sorted order, not the k-th distinct value.
numsholds up to 10⁵ values between −10⁴ and 10⁴, and1 ≤ k ≤ n.- LeetCode asks whether you can solve it without sorting.
- 1 <= k <= nums.length <= 10⁵
- -10⁴ <= nums[i] <= 10⁴
Intuition
To find the kth largest element in an array you only need the k largest values; the order of everything else never matters.
Keep those k values in a min-heap. Its top is the smallest of them, so it is the value every newcomer has to beat. Once every value has been seen, the heap holds the k largest, and its top is exactly the k-th largest.
"k-th largest" or "top k" over a collection points to a heap of size k that keeps the weakest survivor on top: a min-heap for the largest values, a max-heap for the smallest. K Closest Points to Origin (973) and Top K Frequent Elements (347) follow the same plan.
Approach
Before reading on, walk [3,2,1,5,6,4] with k = 2, holding only two values at any time. Which of the two should each new value be compared with?
Two ways to solve it
Seed a min-heap with k values and let every larger value replace the top.
- Guarantee: O(n log k) on every input.
- Input:
numsis never changed. - Streams: works when values arrive one by one.
The safe answer in an interview.
Partition around a random pivot and keep only the side that holds position n − k.
- Speed: linear on average.
- Risk: unlucky pivots make it quadratic.
- Input: rearranges
numsin place.
Faster on average, but harder to get right.
Quickselect is faster on average, but only the heap guarantees its bound and leaves nums untouched. The steps, code and live demo below follow the heap; the quickselect code comes after the demo.
Seed the heap with the first k values
Take nums[:k] and turn it into a min-heap; in the kth largest element in an array Python code, heapq.heapify does this in place in O(k). These are the k largest values seen so far, simply because nothing else has been seen yet.
Compare every other value with the top
For each remaining num, look at heap[0], the smallest of the current top k:
num <= heap[0]: skip it. k values already beat or tie it.num > heap[0]: the top drops out of the top k.heapreplacepops it and pushesnumin one O(log k) step.
Return the top
After the last value, the heap holds the k largest values and its top is the smallest of them: the k-th largest overall. Repeated values need no special care, because each copy is a separate entry in the heap.
Kth Largest Element in an Array solution in Python | C++ | Java
Quickselect (three-way partition)
The k-th largest is the value at index n − k in sorted order. Each round picks a random pivot and splits the current window into smaller, equal and larger parts; if index n − k falls in the equal part the pivot is the answer, otherwise only the side holding it is searched next.
Common pitfalls
Reading the k-th value from the wrong end
nums.sort() return nums[k - 1]
nums.sort() return nums[len(nums) - k]
An ascending sort puts the smallest value first, so nums[k - 1] is the k-th smallest. The k-th largest sits k places from the end.
Removing duplicates first
nums = list(set(nums))
heap = nums[:k] heapq.heapify(heap)
The problem counts repeats. For [3,2,3,1,2,4,5,5,6] with k = 4 the answer is 4, but after removing duplicates the 4th largest of {1, …, 6} is 3.
Complexity
Kth Largest in an Array vs in a Stream
LeetCode 703 has almost the same name, and the same min-heap of size k solves both. The difference is when the answer is needed.
| Kth Largest Element in an Array (215) | Kth Largest Element in a Stream (703) | |
|---|---|---|
| Input | one fixed array | values arrive one at a time through add |
| Answer | once, at the end | after every add |
| Heap | min-heap of size k | min-heap of size k, kept between calls |
| Quickselect | works | no: it needs all the values at once |
Kth Largest Element in an Array FAQ
Why does quickselect sometimes time out on LeetCode 215?
The kth largest element in an array LeetCode tests include arrays full of repeated values. A partition with a fixed pivot and only two sides splits such arrays very unevenly, which costs O(n²). A random pivot with a three-way split (smaller, equal, larger), as in the quickselect code on this page, avoids it.