Python solution
Starting with the bottom left corner of the matrix, if the current element curr equals target, we return True. If curr is larger than target, than since any ele
Starting with the bottom left corner of the matrix, if the current element `curr` equals `target`, we return `True`. If `curr` is larger than `target`, than since any element to the right of `curr` (in the same row) is larger than `curr`, we don\'t need to consider them, so we deduct the row index by 1 (move up by 1 row). By the same token, if `curr` is smaller than `target`, we increase the column index by 1 (move right by 1 column). Repeat the above steps until we find `target` in which case we return `True` or move out of `matrix` in which case we return `False`.\n\nTime complexity: O(m+n), space complexity: O(1).\n```\nclass Solution(object):\n    def searchMatrix(self, matrix, target):\n        """\n        :type matrix: List[List[int]]\n        :type target: int\n        :rtype: bool\n        """\n        m = len(matrix)\n        if m == 0:\n            return False\n        n = len(matrix[0])\n        if n == 0:\n            return False\n        y = m-1\n        x = 0\n        while x < n and y >= 0:\n            if matrix[y][x] == target:\n                return True\n            elif matrix[y][x] < target:\n                x += 1\n            else:\n                y -= 1\n        return False\n```
[]