Repository navigation
097 — Kth Largest Element in an Array
LeetCode 215 · Medium. Given an integer array nums and an integer k, return the kth largest element in the array — the kth largest in sorted order, not the kth distinct value.
This is chapter 94's streaming problem with the "streaming" part removed: you're handed the whole array up front instead of one number at a time, and asked for a single position in the sorted-descending order. Since it's a one-shot question rather than a repeated one, you could just sort everything and read off the answer — but the same shortlist trick from the streaming version still applies and still wins: you only ever need the k largest values, not a full ranking of all n.
"Kth largest element", full stop, is the single most direct heap cue there is — no streaming, no extra context needed. Whenever a problem statement names a specific rank ("kth largest," "kth smallest") rather than asking for the entire sorted order, that's a heap of bounded size k, not a full sort.
Sort the whole array ascending and index directly to the kth-from-the-end position.
func findKthLargestBruteForce(_ nums: [Int], _ k: Int) -> Int {
let sorted = nums.sorted()
return sorted[sorted.count - k]
}
// smoke test
print(findKthLargestBruteForce([3, 2, 1, 5, 6, 4], 2)) // 5
print(findKthLargestBruteForce([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) // 4
print(findKthLargestBruteForce([7], 1)) // 7Big-O: O(n log n) — sorting the entire array to read a single position out of it. O(n) extra space for the sorted copy.
Maintain a min-heap capped at size k — the same shape used in chapter 94 for the streaming version, just run once over a fixed array instead of once per incoming value. When every element has been processed, the root holds exactly the kth largest.
struct Heap<T> {
private var elements: [T] = []
private let areInIncreasingOrder: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.areInIncreasingOrder = sort
}
var isEmpty: Bool { elements.isEmpty }
var count: Int { elements.count }
var peek: T? { elements.first }
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func extract() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let top = elements.removeLast()
siftDown(from: 0)
return top
}
private mutating func siftUp(from index: Int) {
var child = index
var parent = (child - 1) / 2
while child > 0 && areInIncreasingOrder(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = (child - 1) / 2
}
}
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = 2 * parent + 1
let right = 2 * parent + 2
var candidate = parent
if left < elements.count && areInIncreasingOrder(elements[left], elements[candidate]) {
candidate = left
}
if right < elements.count && areInIncreasingOrder(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent { return }
elements.swapAt(parent, candidate)
parent = candidate
}
}
}
func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
var heap = Heap<Int>(sort: <) // min-heap: root is the smallest of the k largest kept so far
for num in nums {
heap.insert(num)
if heap.count > k {
_ = heap.extract()
}
}
return heap.peek!
}
// smoke test — same cases as the brute force
print(findKthLargest([3, 2, 1, 5, 6, 4], 2)) // 5
print(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) // 4
print(findKthLargest([7], 1)) // 7Big-O: O(n log k) — every element does one O(log k) heap operation, capped by the heap's fixed size k rather than the full input size n. O(k) space.
Sorting the full array establishes the exact relative order of every element, including the vast majority that the question never asks about. A min-heap capped at size k only ever tracks "are you in the current top k or not?" — a much cheaper question — and its root, the weakest member of that group, is precisely the kth largest by construction. When k is small relative to n, O(n log k) beats O(n log n) outright; when k approaches n, the two converge, which is a useful sanity check on why the heap approach's advantage scales with how "selective" the question is.
(A different O(n)-average technique, quickselect — a partition-based approach related to quicksort — also solves this problem and is worth knowing, but it isn't a heap technique, so it's out of scope for this chapter.)
-
Heaps and Priority Queues — the same
Heap<T>used throughout this category, here as a min-heap capped at sizek. - Top K and Heap Pattern — this problem is the pattern applied at its most literal: "kth largest" is one of the pattern's own named trigger phrases.
- Kth Largest Element in a Stream — the streaming version of this exact idea; the heap-maintenance logic is identical, just invoked once per array element here instead of once per incoming value.
Kth Largest Element in an Array is the streaming problem's one-shot cousin — run the same size-k min-heap over every element once, and the root is your answer when you're done.
- Why does
findKthLargestprocess the entire array before readingheap.peek!, whereasKthLargest.add(chapter 94) returns an answer after every single insertion? - If
k == nums.count, what value ends up at the heap's root, and why does that make sense given the definition of "kth largest"? - Why is
O(n log k)strictly better thanO(n log n)wheneverk < n, but the two become equal whenk == n?
⬅️ Previous: K Closest Points to Origin · Next: Task Scheduler ➡️