Find kth smallest in sorted 2D matrix

You are given an n x m matrix of integers where each row and each column is sorted in non-decreasing order.

You are also given an integer k such that 1 <= k <= n * m.

Return the k-th smallest element in the matrix, where elements are ordered by value in non-decreasing order and duplicates are counted according to their occurrences.

Example:

• Input:
  • matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]
  • k = 8
• All elements in sorted order: [1, 5, 9, 10, 11, 12, 13, 13, 15]
• Output: 13 (the 8th element in the sorted list).

Design an algorithm that is more efficient than flattening the matrix and fully sorting all n * m elements.

Find kth Smallest in Sorted 2D Matrix

Constraints

• 1 <= n, m
• Each row of matrix is sorted in non-decreasing order
• Each column of matrix is sorted in non-decreasing order
• 1 <= k <= n * m
• Elements may be negative and may contain duplicates

Hints

1. The answer is always one of the values in the matrix and lies between matrix[0][0] (smallest) and matrix[n-1][m-1] (largest). Binary search over this VALUE range instead of over positions.
2. For a candidate value mid, you need count(elements <= mid). Because rows and columns are sorted, start at the bottom-left corner: if the current cell <= mid, every cell above it in this column also qualifies, so add (row + 1) and move right; otherwise move up.
3. Find the smallest value v for which count(<= v) >= k. That v is the k-th smallest, and binary search converging lo==hi guarantees v is an actual matrix element.