[Python, C++] O(M + N) Explained just walk from Top Right corner
Algorithm:\nHere we do not want to be smart heads, because binary search is not very much faster and not easy to understand. Fastest one is O(min(N, M) * log(ma
# Algorithm:\nHere we do not want to be smart heads, because binary search is not very much faster and not easy to understand. Fastest one is **O(min(N, M) * log(max(N, M) / min(N, M)))**, which you can find here\nhttp://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster\n\nWe going to solve it by **O(N + M)** complexity. \nIdea is that if we go down, all number above and on the left are smaller, while if we go left all number under and on the right are larger, so we basically need to _go down_ if we need number _larger_ and _go left_ if we need _smaller_. Last question os where to start? If we will only go _down_ and _left_, we need to start _at most up and right_ spot, so we don\'t miss enything. Here illustration how we will do that:\n\n# Illustrations:\n### For target `5`:\n![image](https://assets.leetcode.com/users/images/dfc2f727-bfb6-4098-8630-b7e7b8bb86e9_1614070035.582655.png)\n\n### For target 20:\n![image](https://assets.leetcode.com/users/images/10a7c6a7-9f44-41c0-9e61-316f67273a54_1614070050.6790533.png)\n\n## Python code:\n```\nclass Solution:\n  def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n    i, j = 0, len(matrix[0]) - 1\n    while i < len(matrix) and j >= 0:\n      if matrix[i][j] < target:\n        i += 1\n      elif matrix[i][j] > target:\n        j -= 1\n      else:\n        return True\n    return False\n```\n\n## C++ Code:\n```\nclass Solution {\n  public:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n    int i = 0, j = matrix[0].size() - 1;\n    while (i < matrix.size() && j >= 0){\n      if (matrix[i][j] < target){\n        ++i; \n      } else if (matrix[i][j] > target){\n        --j;\n      } else {\n        return true;\n      } \n    }\n    return false;\n    }\n};\n```\n\n### Further reading:\nIf you wonder how **O(min(N, M) * log(max(N, M) / min(N, M)))** looks like: \n![image](https://i.imgur.com/USX7Qrl.gif)\nMore details here: http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster
['C', 'Python']