"O(n log n)" Ruby solution


  • 0

    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.


  • 0
    T

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


  • 0

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


  • 0
    T

    @StefanPochmann Oh of course


Log in to reply
 

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