K-th Largest element in an array
MediumA min-heap of size k
Problem
Return the kth largest element in an unsorted array.
Keep a min-heap of the k biggest seen; its smallest member is the k-th largest.
The idea
Keep the k largest elements seen so far in a min-heap; its root is the smallest of those, so any new element bigger than the root displaces it. After one pass the root is the kth largest, in O(n log k) time and O(k) space.
The trick
- Min-heap for kth largest — the root is the one to evict.
- Quickselect averages O(n) if you can tolerate a worst case of O(n²).
- Sorting is O(n log n) and fine when n is small.
3
2
1
5
6
4
0
1
2
3
4
5
k2
Step 1 of 4. Brute force: find the largest 2 time(s), removing it each round. Values: 3, 2, 1, 5, 6, 4. k 2.
1/4
Brute force
timeO(n·k)spaceO(1)
Select k times.
1for (let r = 0; r < k; r++) {2 const i = indexOfMax(remaining);3 answer = nums[i];4 remove(i);5}Input
- array
- [3, 2, 1, 5, 6, 4]
Memory
- k
- 2
- round
- —
Output
- 1st
- —
- 2nd
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [3, 2, 1, 5, 6, 4], k = 2
- Output:
- 5
- Explanation:
- Sorted, the 2nd biggest is 5.
Example 2
- Input:
- nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
- Output:
- 4
- Explanation:
- The 4th largest value is 4.
Example 3
- Input:
- nums = [1], k = 1
- Output:
- 1
- Explanation:
- Only element is the largest.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.