Find kth smallest in sorted matrix
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an n x n matrix where each row and each column is sorted in nondecreasing order, and an integer k (1 ≤ k ≤ n^
2), return the k-th smallest element in the matrix. Compare approaches using a min-heap over row heads versus value-space binary search with counting, and analyze complexities and edge cases.
Quick Answer: This question evaluates algorithmic problem-solving and data-structure knowledge, focusing on selection in a row-and-column-sorted matrix and the comparative use of min-heaps versus value-space binary search along with time/space complexity and edge-case analysis.
Given an n x n matrix where each row and each column is sorted in non-decreasing order, and an integer k (1 ≤ k ≤ n^2), return the k-th smallest element in the matrix.
Note that it is the k-th smallest element in the sorted order, not the k-th distinct element. Duplicate values count toward k.
A min-heap over the row heads gives an O(k log n) solution: seed the heap with the first element of every row, then pop k times, each time pushing the next element from the same row. An alternative value-space binary search with a counting routine runs in O(n log(max-min)) and counts, for a candidate value x, how many matrix entries are ≤ x by walking from the bottom-left corner.
Example:
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 → 13 (sorted order: 1,5,9,10,11,12,13,13,15; the 8th element is 13).
Constraints
- n == matrix.length == matrix[i].length
- 1 <= n <= 300
- Each row and each column of matrix is sorted in non-decreasing order
- 1 <= k <= n^2
- -10^9 <= matrix[i][j] <= 10^9
Examples
Input: ([[1,5,9],[10,11,13],[12,13,15]], 8)
Expected Output: 13
Explanation: Sorted order: 1,5,9,10,11,12,13,13,15. The 8th smallest is 13 (the second 13).
Input: ([[1,2],[1,3]], 2)
Expected Output: 1
Explanation: Sorted order: 1,1,2,3. Duplicates count, so the 2nd smallest is the second 1.
Hints
- The whole matrix isn't globally sorted, but each row IS sorted. Think of merging n sorted lists (the rows) and stopping after k elements.
- Use a min-heap seeded with the head of each row: (value, rowIndex, colIndex). Pop the smallest, then push the next element from that same row.
- After k pops, the last popped value is the answer. Each value pushed/popped costs O(log n).
- Alternative: binary search on the value range [matrix[0][0], matrix[n-1][n-1]]. For a candidate x, count how many entries are <= x by walking from the bottom-left corner in O(n); shrink the range until you isolate the k-th smallest.