Here's the binary search on values solution:
function kthSmallest(matrix, k)
n := number of rows in matrix
left := matrix[0][0]
right := matrix[n - 1][n - 1]
while left < right
mid := left + (right - left) / 2
count := countLessOrEqual(matrix, mid)
if count < k then
left := mid + 1
else
right := mid
return left
function countLessOrEqual(matrix, target)
n := number of rows in matrix
count := 0
row := n - 1
col := 0
while row ≥ 0 and col < n
if matrix[row][col] ≤ target then
count := count + (row + 1)
col := col + 1
else
row := row - 1
return count
The outer binary search halves the value range, taking iterations. Each iteration calls , which walks the matrix in time. Total: .