Kth smallest element in an array
MediumA max-heap of size k
Problem
Return the kth smallest element in an unsorted array.
Keep a max-heap of the k smallest so far; its top is the k-th smallest.
The idea
The mirror image: keep the k smallest in a max-heap whose root is the largest of them, and evict the root whenever a smaller element arrives. The root is then the kth smallest.
The trick
- Max-heap for kth smallest — the opposite of the kth largest case.
- O(n log k) time, O(k) space.
7
10
4
3
20
15
0
1
2
3
4
5
k3
Step 1 of 5. Brute force: find the smallest 3 time(s), removing it each round. Values: 7, 10, 4, 3, 20, 15. k 3.
1/5
Brute force
timeO(n·k)spaceO(1)
Select k times.
1for (let r = 0; r < k; r++) {2 const i = indexOfMin(remaining);3 answer = nums[i];4 remove(i);5}Input
- array
- [7, 10, 4, 3, 20, 15]
Memory
- k
- 3
- round
- —
Output
- 1st
- —
- 2nd
- —
- 3rd
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [7, 10, 4, 3, 20, 15], k = 3
- Output:
- 7
- Explanation:
- Sorted, the 3rd smallest is 7.
Example 2
- Input:
- nums = [7, 10, 4, 20, 15], k = 4
- Output:
- 15
- Explanation:
- The 4th smallest is 15.
Example 3
- Input:
- nums = [1], k = 1
- Output:
- 1
- Explanation:
- Only element.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.