[Python] O(m + n) solution, explained
Let us consider the following example and discuss the algorithm.\n\n| 1  | 4  | 7  | 11 | 15 |\n|----|----|----|----|----|\n| 2  | 5  | 8  | 12 | 19 |\n| 3  | 6
Let us consider the following example and discuss the algorithm.\n\n| 1  | 4  | 7  | 11 | 15 |\n|----|----|----|----|----|\n| **2**  | **5**  | **8**  | **12** | **19** |\n| **3**  | **6**  | **9**  | **16** | **22** |\n| **10** | **13** | **14** | **17** | **24** |\n| **18** | **21** | **23** | **26** | **30** |\n\nLet us start with element on the top right corner and on each step we decide where we can go.\n\n1. Current number is equal to **15**, and `target = 5`, where can we go? All numbers above `15` is more than `15`, so we can eliminate last column and go to the left.\n2. Current number is equal to **11** and again it is bigger than `target = 5`, so we eliminate column and go to the left\n3. Current number is equal to **7**, go to the left.\n4. Current number is **4**, now it is smaller than target, so we can eliminate first row: elements to the left is smaller than `4` and elements to the right already eliminated in columns.\n5. Current number is **5** and we found our target.\n\nIt also can happen, that we do not found number, in this case we need to terminate, when we can not move anymore.\n\n**Complexity**: time complexity is `O(m + n)`, where `m, n` are number of columns and rows: on each step we eliminate either row or column. Space complexity is `O(1)`.\n\n```\nclass Solution:\n    def searchMatrix(self, matrix, target):\n        x, y = len(matrix[0]) - 1, 0\n        while x >= 0 and y < len(matrix):\n            if matrix[y][x] > target:\n                x -= 1\n            elif matrix[y][x] < target:\n                y += 1\n            else:\n                return True\n        return False\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
[]