Search a 2D Matrix

'''
Logic:
remove a row or column in each comparison until an element is found.
if top-right element is greater than x then we can't go downwards because
whole column will have a greater elements so only one option left,go left
side and same goes for each position of array.
Time complexity: O(n+m)
'''
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        i=0
        j=len(matrix[0])-1
        while i<len(matrix) and j>=0:
            if matrix[i][j]==target:
                return True
            if matrix[i][j]>target:
                j-=1
            else:
                i+=1
        return False