Start from bottom-left / top-right - Time O(m+n)
The Brute Force solution takes time O(m * n).\n\nTo optimize,  let\'s observe how we can take advantage of the matrix\'s property.\n\n1. if there is only one ro
The Brute Force solution takes time O(m * n).\n\nTo optimize,  let\'s observe how we can take advantage of the matrix\'s property.\n```\n1. if there is only one row, if curDigit \n                >  target, we check digits to its left\n                <  target, we check digits to its right\n2. if there is only one col, if curDigit \n                >  target, we check digits on its top\n                <  target, we check digits on its bottom\n3. if a curDigit is at the cross of a row and a col,\n\t    if curDigit \n                >  target, we check digits to its left AND on its top\n                <  target, we check digits to its right AND on its bottom\n\t\t\t\t\n        BUT if we traverse the matrix from the bottom-left corner, then we only have to move top / right, since other digits have been invalidated already, that is,\n\t    if curDigit\n                >  target, we check digits to its top\n                <  target, we check digits on its right\n\t\t\t\t\n        OR if we traverse the matrix from the top-right corner, then we only have to move bottom / left, since other digits have been invalidated already, that is,\n\t    if curDigit\n                >  target, we check digits to its left\n                <  target, we check digits on its bottom\n```\nThis approach takes time O(m + n).\n\n****\n**Bottom-left**\n```\nclass Solution {\n    public boolean searchMatrix(int[][] matrix, int target) { \n        int rows = matrix.length, cols = matrix[0].length; \n        \n        int i = rows - 1, j = 0; // Starts at bottom-left\n        \n        while (i >= 0 && j < cols) {\n            if (matrix[i][j] == target) {\n                return true;\n            } else if (matrix[i][j] > target) {\n                i--;\n            } else {\n                j++;\n            }\n        }\n        \n        return false;\n    }\n}\n```\n**Top-right**\n```\nclass Solution {\n    public boolean searchMatrix(int[][] matrix, int target) { \n        int rows = matrix.length, cols = matrix[0].length; \n        \n        int i = 0, j = cols - 1; // Starts at top-right\n        \n        while (j >= 0 && i < rows) {\n            if (matrix[i][j] == target) {\n                return true;\n            } else if (matrix[i][j] > target) {\n                j--;\n            } else {\n                i++;\n            }\n        }\n        \n        return false;\n    }\n}\n```\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
[]