K-th Smallest Element in a Sorted Matrix
Problem statement
You are given an $m \times n$ matrix where each row and each column is sorted in nondecreasing order. Given an integer $k$, return the $k$-th smallest element in the matrix.
Your algorithm should run in $O(k \log(\min(m, n)))$ time and use $O(\min(m, n))$ space.
Constraints:
- $1 \leq m, n \leq 300$
- $-10^9 \leq \text{matrix}[i][j] \leq 10^9$
- All rows and all columns are sorted in nondecreasing order
- $1 \leq k \leq m \times n$
Example 1:
Input: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Output: 13
Explanation: The elements in sorted order are $[1, 5, 9, 10, 11, 12, 13, 13, 15]$. The 8th smallest is $13$.
Example 2:
Input: matrix = [[1, 2], [1, 3]], k = 2
Output: 1
Explanation: The elements in sorted order are $[1, 1, 2, 3]$. The 2nd smallest is $1$.
Example 3:
Input: matrix = [[-5]], k = 1
Output: -5
Show hint
Which classic merging pattern applies when you have several already-sorted sequences and need only the first few outputs?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.