How do you find the k-th largest element in an array?

Difficulty: 5/10

selection algorithm, heap, quickselect

K-th Largest Element

Two common approaches are a min-heap of size k and Quickselect. The heap approach maintains the k largest elements seen so far and keeps the smallest of them at the root, giving O(n log k) time. Quickselect partitions around a pivot and has O(n) expected time with O(n²) worst case.

javascript

1
Min-heap of size k: O(n log k) time, O(k) space.
2
Quickselect: O(n) expected time.
3
Quickselect worst case: O(n²).
4
For small k, the heap is often simple and efficient.
5
Quickselect is attractive when average linear-time selection is desired.

Scenario Questions

0-2 years experience

Follow-up Questions