Hi, @zmzkee Thanks for the question. I'd better make it clear for how to use Binary Search in this qustion.

about binary search, why lo must in matrix?

In the post there is a section, it happens to fit this problem.

This snippet of code is aim to find the first x for which p(x) is true

Suppose matrix = [ [1,7], [8, 10] ] and k=2.

Using Binary Search, we should

Define the Search space: [1..10] Design the predict: p(x) is count( (numbers in matrix) <= x ) >= kSo in the problem, we are going to find the first element x for which p(x) is true, for which count of numbers in [ [1,7], [8, 10] ] less or equal than x just >=2.

The element (lo) must be in the matrix to be the first one to make the prediction truth.

In case my code in "BINARY SEARCH (SOLUTION)" is not clear enough, I've rewritten it.

def kth_smallest(matrix, k) lo, hi = matrix[0][0], matrix[-1][-1] p = ->(x) { count = 0 matrix.each do |row| # b-searching (equals: count += row.count {|num| num <= x}) count += ( (0..row.count-1).bsearch{|i| row[i] > x } or row.count ) end count >= k } while lo < hi mid = (lo+hi)/2 if p[mid] hi = mid else lo = mid + 1 end end return lo end