Appearance
4.17.4 — Kth Largest Element in an Array
LeetCode 215 · Medium
The problem
Return the k-th largest element. This is the k-th largest in sorted order, not the k-th distinct value.
[3,2,1,5,6,4], k = 2 → 5
[3,2,3,1,2,4,5,5,6], k = 4 → 4Up to 100,000 elements. The follow-up asks you to do it without sorting.
The pattern
This is the pure selection problem: find the element that would sit at a given position if the array were sorted, without sorting it.
Three answers, and knowing all three plus the condition that picks each is the point of this problem.
Solution 1 — sort
python
return sorted(nums)[-k]O(n \log n). Correct, one line, and the right thing to say first.
The waste: sorting establishes the position of every element, and you asked about one.
Solution 2 — a size-k min-heap
Keep the k largest seen so far; the root is the k-th largest.
python
import heapq
class Solution:
def findKthLargest(self, 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]O(n \log k) time, O(k) space. The only version that works on a stream.
Python has this in one line — heapq.nlargest(k, nums)[-1] — which uses a size-k heap internally. Know both.
Solution 3 — quickselect, O(n) average
Partition the array around a pivot, exactly as quicksort does: everything smaller goes left, everything larger goes right, and the pivot lands in its final sorted position.
Then — and this is the whole idea — look at where the pivot landed. If that is the position you wanted, you are done. If not, the answer is on one side only, so recurse into that side and ignore the other completely.
Quicksort recurses into both halves. Quickselect recurses into one. That difference is what turns O(n \log n) into O(n).
python
import random
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
target = len(nums) - k # k-th largest = this index when sorted
def partition(lo: int, hi: int) -> int:
p = random.randint(lo, hi) # random pivot
nums[p], nums[hi] = nums[hi], nums[p]
pivot = nums[hi]
store = lo
for i in range(lo, hi):
if nums[i] < pivot:
nums[store], nums[i] = nums[i], nums[store]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
return store # final home of the pivot
lo, hi = 0, len(nums) - 1
while True:
p = partition(lo, hi)
if p == target:
return nums[p]
if p < target:
lo = p + 1
else:
hi = p - 1ts
function findKthLargest(nums: number[], k: number): number {
const target = nums.length - k;
function partition(lo: number, hi: number): number {
const p = lo + Math.floor(Math.random() * (hi - lo + 1));
[nums[p], nums[hi]] = [nums[hi], nums[p]];
const pivot = nums[hi];
let store = lo;
for (let i = lo; i < hi; i++) {
if (nums[i] < pivot) {
[nums[store], nums[i]] = [nums[i], nums[store]];
store++;
}
}
[nums[store], nums[hi]] = [nums[hi], nums[store]];
return store;
}
let lo = 0, hi = nums.length - 1;
while (true) {
const p = partition(lo, hi);
if (p === target) return nums[p];
if (p < target) lo = p + 1;
else hi = p - 1;
}
}target = len(nums) - k. The largest element sits at index n−1 when sorted, the second largest at n−2, so the k-th largest is at n−k. Work this out on paper once rather than guessing.
The random pivot is not decoration. With a fixed pivot such as the last element, a sorted input produces partitions of size n−1 every time, giving O(n^2). Randomising makes that case vanishingly unlikely. Say this out loud — it is the difference between knowing the algorithm and knowing why it works in practice.
Iterative rather than recursive, because there is only ever one side to continue with, so no call stack is needed. O(1) space.
Why the average is O(n)
A good pivot splits the array roughly in half. So the work is:
n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \cdots < 2n
Each level only processes one side, and the sizes halve. The whole sum is bounded by 2n, which is O(n).
Quicksort processes both sides at each level, so each level costs O(n) in total across \log n levels, giving O(n \log n).
The worst case is O(n^2), when every pivot is the smallest or largest remaining element. Randomisation makes it improbable. There is an algorithm called median of medians that guarantees O(n) worst case, but its constant factor is bad enough that nobody uses it in practice. Naming it is enough.
Choosing between them
| time | space | mutates input | works on a stream | |
|---|---|---|---|---|
| sort | O(n \log n) | O(n) | maybe | no |
| size-k heap | O(n \log k) | O(k) | no | yes |
| quickselect | O(n) average | O(1) | yes | no |
Sort if it is fast enough. Heap if the data streams or memory is tight. Quickselect if you need the best time and may reorder the input.
Where this goes next
- K Closest Points to Origin — the same three solutions on distances. 4.17.3.
- Median of a large array — quickselect with
k = n/2. - Wiggle Sort II — quickselect to find the median, then place elements around it.
std::nth_elementin C++ is quickselect.numpy.partitionin Python is too. Knowing that the standard library exposes this operation is worth a sentence.
What the interviewer will push on
"Can you avoid sorting?" Heap for O(n \log k), quickselect for O(n) average.
"Why is quickselect O(n) when quicksort is O(n \log n)?" One side instead of two; the sizes halve and sum to 2n.
"What is quickselect's worst case, and what do you do about it?" O(n^2), fixed in practice by a random pivot. Median of medians guarantees linear but is slow in practice.
"Which index is the k-th largest?" n − k. Derive it rather than guessing.
"What if the data does not fit in memory?" The size-k heap, since it holds only k items at a time.
One thing to volunteer: give all three solutions with their trade-offs in about twenty seconds before writing anything. That comparison is the answer to this problem; the code for any single one of them is routine.
Next: 4.17.5 Task Scheduler — a heap simulation with a cooldown, and a formula that removes the heap entirely.