Accepted Ruby O(n*log(m)) code


  • 0
    O

    As all elements in a row and columns are sorted we can say that binary search on a row will take O(log(m)).
    As we repeated it n times then whole search will take O(n*log(m)) time.

    # @param {Integer[][]} matrix
    # @param {Integer} target
    # @return {Boolean}
    def search_matrix(matrix, target)
      if matrix.empty?
        return false
      end
      n = matrix.size-1
      m = matrix[0].size-1
      i = 0
      is_exists = false
      while i <= n && !is_exists
        is_exists = binary_search(matrix[i], target, 0, m)
        i+=1
      end
      return is_exists
    end
    
    def binary_search(array, target, l, r)
      if l > r
        return false
      end
      mid = (l+r)/2
      e = array[mid]
      if e == target
        return true
      end
      if target > e
        binary_search(array, target, mid+1, r)
      else
        binary_search(array, target, l, mid-1)
      end
    end```

Log in to reply
 

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