LeetCode: 240. Search a 2D Matrix II

Several different solutions

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        j = bisect_right(matrix[0], target) - 1
        i = bisect_right([mat[0] for mat in matrix], target) - 1
        while i >= 0 and j >= 0:
            if matrix[i][j] < target:
                return False
            for k in range(0, i+1):
                if matrix[k][j] == target:
                    return True
            for k in range(0, j+1):
                if matrix[i][k] == target:
                    return True
            i -= 1
            j -= 1

O(NlogM)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for mat in matrix:
            if mat[0] <= target <= mat[-1]:
                l, r = 0, len(mat) - 1
                while l <= r:
                    mid = (l+r) // 2
                    if mat[mid] == target:
                        return True
                    if mat[mid] < target:
                        l = mid + 1
                    else:
                        r = mid - 1
        return False

O(N+M)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        y, x = len(matrix) - 1, 0
        while y >= 0 and x <= len(matrix[0]) - 1:
            if matrix[y][x] == target:
                return True
            if matrix[y][x] > target:
                y -= 1
            else:
                x += 1
        return False