Ruby binary search


  • 1

    Got the algorithm idea from ruichang.


    Solution 1

    def min_area(image, i, j)
      m, n = image.size, image[0].size
      top    =  (0..i).bsearch { |i|  image[i].include?('1') }
      bottom = (i...m).bsearch { |i| !image[i].include?('1') } || m
      left   =  (0..j).bsearch { |j|  image.any? { |row| row[j] == '1' } }
      right  = (j...n).bsearch { |j| !image.any? { |row| row[j] == '1' } } || n
      (bottom - top) * (right - left)
    end
    

    Solution 2

    def min_area(image, i, j)
        top, bottom = [0..i, (image.size-1).downto(i).to_a].map {
            |range| range.bsearch { |i| image[i].include? '1' }
        }
        left, right = [0..j, (image[0].size-1).downto(j).to_a].map {
            |range| range.bsearch { |j| image.any? { |row| row[j] == '1' } }
        }
        (bottom - top + 1) * (right - left + 1)
    end

Log in to reply
 

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