Algorithms and Data Structures · Middle · Question 11 of 75
How do you find the k largest elements of a large array efficiently?
- ✓Correct answer: Keep a min-heap of size k and replace its root when you see a larger value
- 2Put all elements into a
Setand take the first k - 3Sort the whole array in descending order every time a value arrives
Explanation
The heap always holds the k largest seen so far, and its root is the smallest of them. The total cost is O(n log k), which beats sorting (O(n log n)) when k is small, and works on streams too.