K-th Smallest Element in a Sorted Matrix

Reported in interviews at Headlands Technologies Jane Street Meta Reddit

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.

Related free problems