Kth Smallest Element in a Sorted Matrix

Given a matrix where every row and every column is sorted in nondecreasing order, return the kth smallest element. A min heap over the frontiers of each row gives an efficient solution.

Input Format

matrix = sorted matrix, k = rank

Output Format

kth smallest value in the matrix

Constraints

  • 1 <= matrix.length, matrix[i].length <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • Each row and column is sorted ascending

Examples

Example 1:

Input:

matrix = [[1,5,9],[10,11,13],[12,13,15]]
k = 8

Output:

13

Explanation:

The 8th smallest value in the matrix is 13.

Example 2:

Input:

matrix = [[1,2],[1,3]]
k = 2

Output:

1

Explanation:

The sorted sequence is [1,1,2,3].

Loading...
Kth Smallest Element in a Sorted Matrix - Heap