Kth Smallest Element in a Sorted Matrix

Problem Given an n x n matrix with each row and column sorted ascending, return the kth smallest element.

Input / Output

• Input: matrix, int k (1 <= k <= n^2). Output: kth smallest value.

Constraints

• n up to 300; better than O(n^2 log n) (flatten + sort) is expected.

Example

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

Expected approach

• Min-heap over row frontiers: seed with each row's first element, pop k times pushing the popped element's right neighbor — O(k log n).
• Binary search on VALUE range [min, max]: count elements <= mid via the staircase walk from bottom-left (O(n) per count); shrink to the smallest value with count >= k — O(n log(max−min)), the answer interviewers push toward. Contrast the two and explain why the value-space search needs no sorted flattening.