DSA problem
Kth Smallest Element in a Sorted Matrix
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k-th smallest element in the matrix. Note that it is the k-th smallest element in sorted order, not the k-th distinct element.
The naive approach flattens the matrix into a single array of n * n elements, sorts it, and indexes position k - 1. That solution runs in O(n^2 log n) time and O(n^2) space, completely ignoring the matrix's existing sorted structure.
A much better idea treats each row as one of n sorted streams. Because every row is already sorted in ascending order, we can apply the classic k-way merge pattern. A min-heap seeded with the first element of every row gives us O(1) access to the global minimum; popping it and pushing its row's next element lets us walk through the merged sequence in ascending order, one element per pop.
The optimal heap-based solution starts by pushing (matrix[r][0], r, 0) for every row r. Then it pops the smallest entry k times. After each pop (val, r, c), if c + 1 < n, push (matrix[r][c + 1], r, c + 1). The k-th popped value is the answer. The heap holds at most n entries, so each operation costs O(log n) and total work is O(k log n) — a major win when k is much smaller than n^2.
An alternative O(n log(max - min)) solution binary-searches on the value range: for each midpoint, count how many matrix entries are <= mid using the matrix's monotonicity (start in the bottom-left and step right when the count goes up, up when it doesn't). That approach is strictly better asymptotically but the heap version is far cleaner to write and reason about, which is why we present it as the canonical solution.
Examples
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 813matrix = [[-5]], k = 1-5matrix = [[1,2],[1,3]], k = 21Constraints
- n == matrix.length == matrix[i].length
- 1 <= n <= 300
- -10^9 <= matrix[i][j] <= 10^9
- All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
- 1 <= k <= n^2
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.