TL;DR
Min-heap of size k, O(n log k) time / O(k) space — with quickselect (average O(n)) and counting sort (O(n + range)) as the follow-up answers.
Approach 1 — Brute force (sort)
Sort ascending; the k-th largest sits k positions from the end.
from typing import List
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return sorted(nums)[len(nums) - k]
O(n log n) time, O(n) space. At n = 10^5 this passes easily — the constraints don’t kill it, the follow-up does: you sorted 10^5 elements to extract one, and the interviewer will ask what you can do about that.
Approach 2 — Min-heap of size k
The insight: the k-th largest is the smallest of the k largest. Sweep once, keeping a min-heap of the k largest values so far; a new value either beats the root (evict and enter) or can never matter. A binary min-heap is a complete tree, stored flat in an array, whose root is always the minimum — O(log size) push/pop, O(1) peek.
import heapq
from typing import List
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = nums[:k]
heapq.heapify(heap)
for x in nums[k:]:
if x > heap[0]:
heapq.heapreplace(heap, x)
return heap[0]
Walkthrough of nums = [3, 2, 1, 5, 6, 4], k = 2:
- Heapify
[3, 2] → heap {2, 3}, root 2.
1: not > 2 → skip.5: > 2 → replace root → {3, 5}.6: > 3 → replace root → {5, 6}.4: not > 5 → skip.- Return root 5. ✓
Complexity: O(k) heapify + (n − k) comparisons, each with at most one O(log k) replace → O(n log k) time, O(k) space. (Equivalent one-liner: heapq.nlargest(k, nums)[-1], which uses the same bounded heap internally.)
Approach 3 — Quickselect (average O(n))
The insight: the k-th largest is the element at sorted index n − k. Quickselect (Hoare’s selection algorithm — quicksort that recurses into only one side) partitions around a pivot and then knows exactly which side that index lives in, discarding the other side entirely. Random pivots make the expected work n + n/2 + n/4 + ⋯ = O(n). A 3-way partition (< pivot | == pivot | > pivot) keeps duplicate-heavy inputs linear too.
import random
from typing import List
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
target = len(nums) - k # index in ascending order
lo, hi = 0, len(nums) - 1
while True:
pivot = nums[random.randint(lo, hi)]
i, eq, j = lo, lo, hi # 3-way partition
while eq <= j:
if nums[eq] < pivot:
nums[i], nums[eq] = nums[eq], nums[i]
i += 1
eq += 1
elif nums[eq] > pivot:
nums[eq], nums[j] = nums[j], nums[eq]
j -= 1
else:
eq += 1
if target < i:
hi = i - 1 # answer in the < block
elif target > j:
lo = j + 1 # answer in the > block
else:
return pivot # answer inside the == block
Walkthrough of [3, 2, 1, 5, 6, 4], k = 2 → target = 4. Say the random pivot is 4: partition gives < 4 block [3, 2, 1] (indices 0–2), == 4 block at index 3, > 4 block [5, 6] at indices 4–5, so i = 3, j = 3. Since target = 4 > j = 3, recurse right with lo = 4. Next round on [5, 6]: pivot say 5 → == block at index 4, > block at 5; target = 4 falls in the == block → return 5. ✓
Complexity: expected O(n) time, O(n²) worst case (randomization makes that astronomically unlikely); O(1) extra space, but it shuffles the input in place.
Approach 4 — Counting sort over the value range
The insight: values live in [−10^4, 10^4] — only 2·10^4 + 1 distinct possibilities, far fewer than n can be. Counting sort tallies occurrences per value, then walks the tally from the top, decrementing k by each bucket’s count until it crosses zero. No comparisons at all.
from typing import List
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
OFFSET = 10_000
counts = [0] * 20_001
for x in nums:
counts[x + OFFSET] += 1
remaining = k
for v in range(20_000, -1, -1):
remaining -= counts[v]
if remaining <= 0:
return v - OFFSET
return -1 # unreachable given constraints
Walkthrough of [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4: counts (showing nonzero) — 1:1, 2:2, 3:2, 4:1, 5:2, 6:1. Walk down: v=6 → remaining 3; v=5 → remaining 1; v=4 → remaining 0 → return 4. ✓
Complexity: O(n + R) time and O(R) space with R = 20 001 — genuinely linear here, at the price of depending on the value range rather than n.
Common pitfalls
- “K-th largest” means with duplicates counted —
[5, 5, 4], k = 2 is 5, not 4. (K-th distinct is a different problem.)
- Min-heap vs max-heap confusion: for k-largest keep a min-heap (root = weakest member = answer); a max-heap of everything needs k pops instead.
- Quickselect with a fixed pivot (first/last element) hits O(n²) on sorted input, and 2-way (Lomuto) partition hits O(n²) on all-equal arrays — randomize and use a 3-way partition.
- Translating “k-th largest” to ascending index: it’s
n − k, not k or k − 1.
Pattern takeaway
This is the archetype of the selection ladder — sort O(n log n), bounded heap O(n log k), quickselect average O(n), and (when the key range is small) counting sort O(n + R). Say the whole ladder in interviews, then pick: heap for streams and small k, quickselect for in-memory one-shots, counting when the constraints whisper “the values are tiny.” The heap invariant to internalize: to keep the k largest, expose the smallest of them.