Python Very clear explanation with drawing O(m+n).
Hello,\n\nTime complexity: O(m+n), where m is the number of rows, n is the number of columns.\nSpace complexity: O(1).\n\nclass Solution:\n    def searchMatrix(
Hello,\n\n**Time complexity: O(m+n), where m is the number of rows, n is the number of columns.\nSpace complexity: O(1).**\n```\nclass Solution:\n    def searchMatrix(self, matrix, target):\n        rows, cols = len(matrix), len(matrix[0])\n        \n        top = 0\n        right = cols-1\n        \n        bottom = rows-1\n        left = 0\n\n        while bottom >= top and left <= right:\n            if matrix[bottom][left] == target:\n                return True\n            if matrix[bottom][left] > target:\n                bottom -= 1\n            elif matrix[bottom][left] < target:\n                left += 1\n        return False\n```\n\nThe idea is to start from **Bottom Left** and then go up or right depending on the current **Bottom Left**  value.\n\nIf the current **Bottom Left** value == target then return True.\n\nIf the current **Bottom Left** value is > target then go up by 1 (to ignore the whole row since this value is also samller than all the numbers on the right of it).\n\nIf the current **Bottom Left** value is < target then go right by 1 (because the value might still be in this row so we **do not** ignore it).\n\nThe current **Bottom Left** value changes everytime we go up or right.\n\nWe go up by doing **bottom-1**.\nWe go right by doing **left+1**.\n\nBreak the loop when the **left is > right** (which is **cols-1**)\nor\nBreak the loop when the **bottom is < top** (which is **0**).\n\n**Examples with drawing:**\n1. **matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5**\n![image](https://assets.leetcode.com/users/images/8429db28-a5d5-4d31-ae66-8c8da6fca8cc_1660979929.5496066.jpeg)\n\n2. **matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20**\n![dc25cd0e-b2ba-4f4d-8814-4383cf61e61b_1660981277.3080633.jpeg](https://assets.leetcode.com/users/images/7681ca72-0427-429e-8509-1bc61e1cc415_1665947254.116068.jpeg)\n\n\n\n3. **An example of the worst case which is O(m+n) (m: number of rows, n: number of columns)**\n![image](https://assets.leetcode.com/users/images/5220ec80-ac24-4226-b744-9a92d4bd481c_1660981040.4934547.jpeg)
['Python', 'Python3']