A/C Python solution, easy to understand, beat 1.7%


  • 0
    W
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        #print "matrix = ", matrix
        #print "target = ", target
    
        numRows = len(matrix)
        #print "numRows = ", numRows
        if numRows < 1:
            return False
        numCols = len(matrix[0])
        if numCols < 1:
            return False
    
        #print "numRows = ", numRows, " numCols = ", numCols
    
        lower_bound_idx_row, lower_bound_idx_col = 0, 0
        upper_bound_idx_row, upper_bound_idx_col = numRows - 1,  numCols - 1
    
    
        #print "lower_bound_idx_row = ", lower_bound_idx_row, " lower_bound_idx_col = ", lower_bound_idx_col
        #print "upper_bound_idx_row = ", upper_bound_idx_row, " upper_bound_idx_col = ", upper_bound_idx_col
    
        def verifyIdx(needVerifyIdxRow, needVerifyIdxCol):
            if needVerifyIdxRow < 0 or needVerifyIdxRow >= numRows or needVerifyIdxCol < 0 or needVerifyIdxCol >= numCols:
                return False
            else:
                return True
    
    
        while (matrix[lower_bound_idx_row][lower_bound_idx_col] < target):
    
            if verifyIdx(lower_bound_idx_row+1, lower_bound_idx_col+1) == True and matrix[lower_bound_idx_row+1][lower_bound_idx_col+1] < target:
                lower_bound_idx_row += 1
                lower_bound_idx_col += 1
            else:
                break
        #print "after modify, lower_bound_idx_row = ", lower_bound_idx_row, " lower_bound_idx_col = ", lower_bound_idx_col
    
        while (matrix[upper_bound_idx_row][upper_bound_idx_col] > target):
    
            if verifyIdx(upper_bound_idx_row-1, upper_bound_idx_col-1) == True and matrix[upper_bound_idx_row-1][upper_bound_idx_col-1] > target:
                upper_bound_idx_row -= 1
                upper_bound_idx_col -= 1
            else:
                break
        #print "after modify, upper_bound_idx_row = ", upper_bound_idx_row, " upper_bound_idx_col = ", upper_bound_idx_col
    
        for curRow in range(numRows):
            for curCol in range(numCols):
                #print "curRow = ", curRow, " curCol = ", curCol
    
                if (curRow < lower_bound_idx_row and curCol < lower_bound_idx_col) or (curRow > upper_bound_idx_row and curCol > upper_bound_idx_col):
                    #print "this is out or range, don't test"
                    continue
    
                if matrix[curRow][curCol] == target:
                    return True
    
        return False

Log in to reply
 

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