matrix is an n × n grid of integers in which every row goes from smallest to largest (left to right) and so does every column (top to bottom). Equal neighbours are allowed.
Write kth_smallest(matrix: list[list[int]], k: int) -> int that returns the value that would sit at position k (1-based) if all n² values were put in one list and sorted from smallest to largest. Duplicates count separately.
Examples:
matrix = [[1, 4, 9],
[2, 6, 10],
[5, 8, 13]]
kth_smallest(matrix, 5) == 6: in order, the values are 1, 2, 4, 5, 6, 8, 9, 10, 13, and the 5th is 6. Notice that 6 is not in the first row: the smallest values are spread over the top-left corner.
kth_smallest([[-3, 0], [0, 7]], 3) == 0: sorted, the values are-3, 0, 0, 7. Both 0s count, so the 2nd and the 3rd smallest are both 0.kth_smallest([[11]], 1) == 11
Constraints: 1 <= n <= 300, values -10^9..10^9, 1 <= k <= n². You may assume the rows and columns really are sorted.
Aim for better than sorting everything: about O(k log n), or O(n log(max - min)). (Flattening the matrix and sorting it passes the tests in Python, since the built-in sort is so fast, but it ignores the order the matrix already has, which is the point of the drill.)
⭐ Bonus: speed tests on 300 × 300 matrices with k near n² earn a star. Looking at the front of all n rows to find each next value is O(k·n), which is too slow there.
Show hint
The smallest value you haven't used yet is always at the front of some row. Keep those row fronts in a min-heap, and after you pop one, push the next value from the same row. Alternatively, guess a value and count how many entries are at most that value, walking a staircase from the bottom-left corner; then binary search on the value.