Find kth Smallest Element in a Sorted Matrix?

int KthSmallest(int[][] matrix, int k)

int n = matrix.Length;

int low = matrix[0][0], high = matrix[n - 1][n - 1];

while (low < high)

Follow on:

int mid = low + (high - low) / 2;

int count = 0, j = n - 1;

for (int i = 0; i < n; i++)

while (j >= 0 && matrix[i][j] > mid)

j--;

count += (j + 1);

if (count < k)

low = mid + 1;

else

high = mid;

return low;

Explanation:

Binary search on values, count how many elements ≤ mid using matrix’s sorted rows/cols.