Questions
43 of 59
How do you find the k-th largest element in an array?
Difficulty: 4/10
K-th Largest Element
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.
Follow-up Questions
- How does Quickselect achieve expected O(n)?
- When is a heap preferable?