Kth Smallest Element in a Sorted Matrix

Problem

You are given an n x n matrix of integers in which every row is sorted in ascending order and every column is sorted in ascending order. Rows do not necessarily chain into one another: the first element of a row may be smaller than the last element of the previous row. Given an integer k, return the k-th smallest value in the matrix, counting duplicates as separate entries (so the sorted order of all n^2 values, position k).

• n is between 1 and 500.
• Cell values are integers between -2,000,000,000 and 2,000,000,000.
• k is between 1 and n^2.

Examples

• matrix = [[2, 6, 8], [3, 7, 12], [9, 14, 20]], k = 5 → 8. Sorted values: 2, 3, 6, 7, 8, 9, 12, 14, 20; the 5th is 8.
• matrix = [[4]], k = 1 → 4.
• matrix = [[3, 5], [3, 8]], k = 2 → 3. Duplicates count separately, so the two 3s occupy positions 1 and 2.

Hints

1. Flattening and sorting is O(n^2 log n). Which structural property is that throwing away?
2. Every row is a sorted list; the k-th smallest across n sorted lists is a merge problem. Alternatively: for a candidate value x, how fast can you count matrix entries <= x?
3. Either a min-heap seeded with each row's first element (pop k times), or binary search on the value range with an O(n) staircase count as the predicate.