198. Kth Smallest Element in a Sorted Matrix

Medium · Heap

Given an n × m matrix where each row and each column is sorted in ascending order, find the kth smallest element in the matrix.

The matrix is guaranteed to be non-empty, and k is guaranteed to be a valid index (1 ≤ k ≤ n × m).

Examples

Example 1
Input: matrix = [[1, 2], [1, 3]], k = 3
Output: 2
Explanation: The sorted elements are [1, 1, 2, 3]. The 3rd smallest is 2.
Example 2
Input: matrix = [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]], k = 8
Output: 8
Explanation: Reading row by row: [1, 2, 3, 4, 5, 6, 7, 8, ...]. The 8th smallest is 8.

Constraints