# "O(n log n)" Ruby solution

• 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.

``````def kth_smallest(matrix, k)
n = matrix.size
(matrix[0][0]..matrix[-1][-1]).bsearch { |x|
matrix.map { |row|
row.bsearch_index { |y| y > x } || n
}.sum >= 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.

Old solution: (from before LeetCode updated to a newer Ruby version):

``````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
``````

• @StefanPochmann Can you write a C++ version? Reading Ruby written by someone who knows the idiosyncrasies of the language may as well be machine code to me.

• @tonytata What about 光速小子's solution?

• @StefanPochmann Oh of course

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.