2 lines O(log m + log n) Ruby


  • 0

    Solution 1 - Find row, then find value

    def search_matrix(matrix, target)
      row = matrix.bsearch { |row| row.last >= target }
      !!row && row.bsearch { |value| value >= target } == target
    end
    

    One-liner version:

    def search_matrix(matrix, target)
      (matrix.bsearch { |r| r[-1] >= target } || []).bsearch { |v| v >= target } == target
    end
    

    Solution 2 - Just one search

    def search_matrix(matrix, target)
      m, n = matrix.size, matrix[0].size
      i = (0...m*n).bsearch { |i| matrix[i/n][i%n] >= target }
      !!i && matrix[i/n][i%n] == target
    end
    

    "Solution" 3 - Inefficient but accepted and short

    Really shouldn't get accepted, though. Just including it because it looks so nice.

    def search_matrix(matrix, target)
      matrix.flatten.include?(target)
    end

Log in to reply
 

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