O(N) Python solution with bisect


  • -1
    Y

    class Solution(object):
    def searchMatrix(self, matrix, target):
    """
    :type matrix: List[List[int]]
    :type target: int
    :rtype: bool
    """
    if not matrix or not matrix[0]:
    return False
    m=len(matrix)
    n=len(matrix[0])
    i=bisect.bisect_left(zip(*matrix)[-1],target)
    if i<m:
    j=bisect.bisect_left(matrix[i],target)
    return matrix[i][j]==target
    else:
    return False


  • 0
    M

    How are we supposed to read that without indentation?

    And what is N? That's not defined anywhere and it can't be n, as this solution is obviously not O(n).

    And since this is only O(mn), you're violating the "Write an efficient algorithm" instruction.


Log in to reply
 

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