#378
Kth Smallest Element in a Sorted Matrix
Medium K-way merge with a min-heap
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In an n×n matrix where every row and column is sorted ascending, return the k-th smallest element.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the k-th smallest number in a matrix with sorted rows and columns.
Why this works: merge the rows like k sorted lists with a min-heap; pop k - 1 times.
Example: [[1,5,9],[10,11,13],[12,13,15]], k = 8
pops: 1, 5, 9, 10, 11, 12, 138th = 13
✦Hints open one at a time
Each row is a sorted list — merge them like "Merge k Sorted Lists".
Start with the first element of each row in a min-heap; pop k − 1 times, pushing the next element of the popped row.
↗Approach
Heap entries are (value, row, col). After k − 1 pops (each followed by pushing the next column of that row), the top is the answer.
</>Solution (Java)
import java.util.*;
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
for (int r = 0; r < Math.min(n, k); r++) heap.offer(new int[]{matrix[r][0], r, 0});
for (int i = 0; i < k - 1; i++) {
int[] top = heap.poll();
int r = top[1], c = top[2];
if (c + 1 < n) heap.offer(new int[]{matrix[r][c + 1], r, c + 1}); // next in that row
}
return heap.peek()[0];
}
}!Common mistake
Flattening and sorting — O(n² log n), ignores the sorted structure. (Binary search on value is another good approach.)
Complexity
- Time: O(k log n).
- Space: O(n).
Topic: Heaps & Priority Queue
🎬 Episodes 64–68: video coming soon