C++✅| Beats 99.74%🔥| O(m+n)🚀| Step By Step Explanation
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \n- The following algorithm aims to search for the target in the matrix, which is a
![Screenshot 2024-04-04 134907.png](https://assets.leetcode.com/users/images/e30864e3-1e9b-4775-94ac-fc79b9062425_1712218933.904733.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- The following algorithm aims to search for the `target` in the matrix, which is assumed to be sorted in both rows and columns. \n- It starts the search from the `top-right` corner of the matrix and iterates through the matrix based on a condition. \n- If the current element equals the `target`, it returns `true`. If the current element is less than the `target`, it moves to the next row to potentially find a larger value. \n- If the current element is greater than the `target`, it moves to the previous column to potentially find a smaller value. If the loop finishes without finding the `target`, it returns `false`. \n- This algorithm exploits the sorted nature of the matrix to efficiently search for the target element. Overall, the code appears to be a concise and effective implementation of the problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n### Initialization:\n- Get the number of rows (`rows`) and columns (`cols`) in the matrix.\n- Initialize two pointers `i` and `j`:\n  - `i` starts from 0, pointing to the first row.\n  - `j` starts from `cols - 1`, pointing to the last column.\n\n### Search Loop:\n- Start a while loop that continues as long as `i` is less than the number of rows and `j` is greater than or equal to 0.\n- Inside the loop:\n  - Check if the current element `matrix[i][j]` is equal to the target value.\n    - If yes, return `true`, indicating that the target value is found.\n  - If the current element is less than the target value:\n    - Increment `i` to move down the matrix (because the current row elements are smaller than the target).\n  - If the current element is greater than the target value:\n    - Decrement `j` to move left in the matrix (because the current column elements are greater than the target).\n\n### Return False:\n- If the loop terminates without finding the target value, return `false`, indicating that the target is not present in the matrix.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    - The time complexity of this algorithm is O(m + n), where \'m\' is the number of rows and \'n\' is the number of columns in the matrix.\n    - In the worst case, both pointers \'i\' and \'j\' traverse through all rows and columns once.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    - The space complexity of this algorithm is O(1), meaning it uses constant extra space regardless of the input size.\n    - The algorithm doesn\'t use any additional data structures that scale with the input size.\n\n# Code\n```\nstatic auto _ = []() {\n    ios::sync_with_stdio(false); \n    cin.tie(nullptr); \n\n    return 0; \n} ();\n\nclass Solution {\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        int rows = matrix.size();\n        int cols = matrix[0].size();\n\n        int i=0;\n        int j=cols-1;\n\n        while(i<rows && j>=0){\n            if(matrix[i][j] == target) return true;\n            else if(matrix[i][j] < target) i++;\n            else j--;\n        }\n        return false;\n    }\n};\n```\n![UPVOTE CAT.jpg](https://assets.leetcode.com/users/images/76628651-9a09-4774-a05a-26be71b40345_1712218952.0598912.jpeg)\n
['Array', 'Divide and Conquer', 'Matrix', 'C++']