O(logm+logn) solution in Python


  • 0
    X
    class Solution:
        # @param matrix, a list of lists of integers
        # @param target, an integer
        # @return a boolean
        def searchMatrix(self, matrix, target):
            n = len(matrix[0])-1
            start = 0
            end = len(matrix)-1
            row = -1
            while start <= end:
                mid = (start+end)//2
                if matrix[mid][n] == target:
                    return True
                if matrix[mid][n] < target:
                    start = mid+1
                    continue
                if matrix[mid][n] > target:
                    if mid == 0:
                        row = mid
                        break
                    elif matrix[mid-1][n] < target:
                        row = mid
                        break
                    else:
                        end = mid -1
                        continue
            if row == -1:
                return False
            start = 0
            end = n
            while start <= end:
                mid = (start+end)//2
                if matrix[row][mid] == target:
                    return True
                if matrix[row][mid] > target:
                    end = mid-1
                    continue
                if matrix[row][mid] < target:
                    start = mid+1
                    continue
            return False

Log in to reply
 

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