Python3     ||     7 lines,  w/ explanation    ||    T/S: 98% / 96%
\nHere\'s the plan:\nWe start in the bottom-left corner, which is matrix[-1][0]. Obviously, the target cell cannot be either below or to the left of this corner
\nHere\'s the plan:\nWe start in the bottom-left corner, which is matrix[-1][0]. Obviously, the target cell cannot be either below or to the left of this corner cell\n                        \nWe move incrementally from the corner such that we do not pass to right of the target\'s column or above its row; we can ensure this by exploiting the sorted rows and columns. \n\nFor example (below), the *target* is 8 and and the corner is 18. So:\n```\n          -- 18 > 8 =>  move up    to 10,\n          -- 10 > 8 =>  move up    to  3,\n          --  3 < 8 =>  move right to  6,\n          --  6 < 8 =>  move right to  9,\n          --  9 > 8 =>  move up    to  8.\n```\n![image](https://assets.leetcode.com/users/images/9e8737fd-576b-47a6-8f22-026b209f0181_1658626054.8534317.jpeg)\n\n```\nclass Solution: \n    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:\n        \n            row, col =   len(matrix)-1, 0        # <-- start at corner\n\n            while row >=0 and col <= len(matrix[0])-1:  \n\n                cell = matrix[row][col]\n\n                if cell > target:    row-= 1    # <-- go up \n                    \n                elif cell < target:  col+= 1    # <-- go right\n                    \n                else: return True               # <-- target found\n\n            return  False\n```\n\n[https://leetcode.com/problems/search-a-2d-matrix-ii/submissions/1269862416/](https://leetcode.com/problems/search-a-2d-matrix-ii/submissions/1269862416/)\n\n\nI could be wrong, but I think that time complexity is *O*(*M* + *N*) and space complexity is *O*(1), in which *M*, *N* ~ `row`, `col`.
['Python', 'Python3']