Inspired by @光速小子's solution. I had roughly the same idea myself, but 光速小子 made it simpler than I thought it would be. This here is pretty much just a translation to Ruby, which I like for its binary search capability (and it would be even nicer if we had a newer Ruby version with `bsearch_index`

).

```
def kth_smallest(matrix, k)
n = matrix.size
(matrix[0][0]..matrix[-1][-1]).bsearch { |x|
matrix.map { |row|
(0...n).bsearch { |j| row[j] > x } || n
}.inject(:+) >= k
}
end
```

**Explanation:** The result is the smallest number `x`

so that the matrix has at least `k`

numbers less than or equal to `x`

. The outer binary search looks for that `x`

. The three lines inside count the numbers less than or equal to `x`

and compare that to `k`

.

**Note:** I put "O(n log n)" in quotes because there's another factor `w`

, where `w`

is the computer's word size (or log(matrix[-1][-1] - matrix[0][0])). Since that's constant, it can somewhat legitimately be ignored, but more appropriately it would be called O(wn log n). Like with radix sort on Wikipedia.