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 = [] # (1)
for n in nums: # (2)
heapq.heappush(heap, n) # (3)
if len(heap) > k: # (4)
heapq.heappop(heap)
return heap[0] # (5)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.
Line by line. (1) An empty heap, which keeps its smallest item at the front. (2) Visit every number once. (3) Push it. (4) If the heap holds more than k numbers, remove the smallest, because it cannot be among the k largest. (5) The heap now holds exactly the k largest numbers, and the smallest of them, at the front, is the k-th largest. This is the same idea as 4.17.1, run over a fixed list. It costs O(n \log k) time and O(k) memory.
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).
Think of Quickselect like looking for a name in a phone book. If you open it to the middle and realize the name you want is alphabetically earlier, you completely tear off the second half of the book and throw it away. You don't bother sorting or organizing the thrown-away half because you know your target isn't there.
python
import random
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
target = len(nums) - k # (6) k-th largest = this index when sorted
def partition(lo: int, hi: int) -> int: # (7)
p = random.randint(lo, hi) # (8) random pivot
nums[p], nums[hi] = nums[hi], nums[p]
pivot = nums[hi] # (9)
store = lo # (10)
for i in range(lo, hi):
if nums[i] < pivot: # (11)
nums[store], nums[i] = nums[i], nums[store]
store += 1
nums[store], nums[hi] = nums[hi], nums[store] # (12)
return store # final home of the pivot
lo, hi = 0, len(nums) - 1 # (13)
while True:
p = partition(lo, hi) # (14)
if p == target: # (15)
return nums[p]
if p < target: # (16)
lo = p + 1
else:
hi = p - 1 # (17)ts
function findKthLargest(nums: number[], k: number): number {
const target = nums.length - k; // (6)
function partition(lo: number, hi: number): number { // (7)
const p = lo + Math.floor(Math.random() * (hi - lo + 1)); // (8)
[nums[p], nums[hi]] = [nums[hi], nums[p]];
const pivot = nums[hi]; // (9)
let store = lo; // (10)
for (let i = lo; i < hi; i++) {
if (nums[i] < pivot) { // (11)
[nums[store], nums[i]] = [nums[i], nums[store]];
store++;
}
}
[nums[store], nums[hi]] = [nums[hi], nums[store]]; // (12)
return store;
}
let lo = 0, hi = nums.length - 1; // (13)
while (true) {
const p = partition(lo, hi); // (14)
if (p === target) return nums[p]; // (15)
if (p < target) lo = p + 1; // (16)
else hi = p - 1; // (17)
}
}Line by line (quickselect)
(6) The position the answer would have in sorted order. In a list sorted from small to large, the largest number sits at position n - 1, the second largest at n - 2, and so the k-th largest at n - k.
(7) partition arranges the stretch from lo to hi around one chosen number, the pivot. Afterwards, everything smaller than the pivot is to its left, everything else is to its right, and the pivot itself sits exactly where it would be in a fully sorted list. The function returns that position.
(8) Choose the pivot at random, and swap it to the end of the stretch so it is out of the way. A random choice is what keeps quickselect fast on average. See the note after this list.
(9) Remember the pivot's value.
(10) store marks where the next small number should go. Everything before store is known to be smaller than the pivot.
(11) Walk the stretch. Each number smaller than the pivot is swapped into position store, and store moves one step right.
(12) Put the pivot right after all the smaller numbers. That is its final sorted position, and we return it.
(13) Start with the whole list.
(14) Partition the current stretch. The pivot lands at position p.
(15) If the pivot landed exactly at target, it is the answer. Every number to its left is smaller and every number to its right is not, so it is exactly the k-th largest.
(16) If the pivot landed left of target, the answer is to its right. Continue with only the right part.
(17) Otherwise the answer is to its left. Continue with only the left part. The other part is never touched again. That is the difference from quicksort, which sorts both parts.
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.
Trace
Let's trace Quickselect for nums = [3,2,1,5,6,4] and k = 2. The sorted index target = 6 - 2 = 4.
lo = 0, hi = 5: Pick a pivot, saynums[hi] = 4. Partitioning moves<4to the left.[3,2,1]are smaller,[5,6]are larger. After swapping,numsbecomes[3,2,1,4,6,5]. The pivot4lands at index3(p = 3).p (3) < target (4), so our target is to the right. We updatelo = 4, hi = 5.lo = 4, hi = 5:nums[4:6]is[6,5]. Pick pivot5. Partitioning puts5at index4.numsbecomes[3,2,1,4,5,6].p = 4.p (4) == target (4). We returnnums[4], which is5. Correct!
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.
Edge cases
k = 1. The answer is the largest number.targetis the last position.kequals the length. The answer is the smallest number.targetis 0.- Repeated numbers, like
[3, 3, 3]. Numbers equal to the pivot go to its right, and the loop still ends, because the pivot's own position is settled every round. - Quickselect changes the order of
nums. If the caller needs their list unchanged, work on a copy.
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.