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
def findKthLargest(nums: List[int], k: int) -> int:
return sorted(nums)[len(nums) - k]
O(n log n) time, O(n) space. This passes at n = 10^5, but you sorted the whole array to extract a single element. That is exactly what the follow-up asks you to improve.
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 seen so far; a new value either beats the root (evict the root, insert the value) or cannot matter. A binary min-heap is a complete tree stored flat in an array, with its minimum always at the root — O(log size) push/pop, O(1) peek.
import heapq
from typing import List
def findKthLargest(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.
The final heap holds the k = 2 largest values, and its root is the answer:
graph TD
A["5 (root = k-th largest)"] --- B["6"]
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 which side that index lives in, discarding the other side. 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.
import random
from typing import List
def findKthLargest(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 the < 4 block [3, 2, 1] (indices 0–2), the == 4 block at index 3, and the > 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 reorders 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, often far fewer than n. Counting sort tallies occurrences per value, then walks the tally from the top, subtracting each bucket’s count from k until k reaches zero. No comparisons.
from typing import List
def findKthLargest(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: nonzero counts — 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 — linear here, at the cost of depending on the value range rather than n.
Common pitfalls
- “K-th largest” counts duplicates:
[5, 5, 4], k = 2 is 5, not 4. K-th distinct is a different problem.
- Min-heap vs max-heap: 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 a 2-way (Lomuto) partition hits O(n²) on all-equal arrays — randomize the pivot and use a 3-way partition.
- Translating “k-th largest” to an ascending index: it is
n − k, not k or k − 1.
Pattern takeaway
Think of a selection ladder: sort O(n log n), bounded heap O(n log k), quickselect average O(n), and counting sort O(n + R) when the key range is small. State the options in an interview, then choose: heap for streams and small k, quickselect for in-memory one-shots, counting sort when the value range is tiny. The heap invariant to remember: to keep the k largest, expose the smallest of them.