Java | TC: O(R+C) | SC: O(1) | Optimal solution using Elimination Strategy
java\n/**\n * Search from Top left corner.\n *\n * If target is less than top left corner, then we can safely reduce the column\n * index as all the below value
```java\n/**\n * Search from Top left corner.\n *\n * If target is less than top left corner, then we can safely reduce the column\n * index as all the below values in column will be greater than the target.\n *\n * Similarly if the target is more than the top left corner, then we can safely\n * increase the row index as all the left values in the row will be smaller than\n * the target.\n *\n * Time Complexity: O(R + C)\n *\n * Space Complexity: O(1)\n *\n * R = Number of rows. C = Number of columns.\n */\nclass Solution {\n    public boolean searchMatrix(int[][] matrix, int target) {\n        if (matrix == null) {\n            throw new IllegalArgumentException("Input is null");\n        }\n        if (matrix.length == 0 || matrix[0].length == 0) {\n            return false;\n        }\n\n        int row = 0;\n        int col = matrix[0].length - 1;\n\n        while (row < matrix.length && col >= 0) {\n            if (matrix[row][col] == target) {\n                return true;\n            }\n            if (target < matrix[row][col]) {\n                col--;\n            } else {\n                row++;\n            }\n        }\n\n        return false;\n    }\n}\n```\n\n---\n\nSolutions to other parts of Search a 2D Matrix question on LeetCode:\n- [74. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/discuss/1511703/Java-or-TC:-O(log(R*C))-or-SC:-O(1)-or-Optimized-binary-search-solution)
['Array', 'Matrix', 'Java']