JAVA O(N+M)
We can take advantage of the fact that our given input input grid is sorted. So if we are at a particular element we are guranteed that all the element to it\'s
We can take advantage of the fact that our given input input grid is sorted. So if we are at a particular element we are guranteed that all the element to it\'s right and to it\'s bottom will be larger that the current element.\nAnd we also know that all the element to it\'s left and to it\'s top will be less than the current element;\n\nSo this potentially allow us to eliminte :\n\tEither all the element below and to the right if our target is less that the current elemet `target < grid[i][j]`\n\tOr we can eliminate all the elements to the left and top if our target is greater that the current     element `target > grid[i][j]`\n\nLet\'s say out target is 6, then: \n![image](https://assets.leetcode.com/users/images/b8b8731d-9862-4d9a-a9fd-5edc47a1a269_1629074320.0377576.png)\n\n\nWe start at first row\'s last index because thats the max possible number that we can get in that row and the least possible element in the last colums. We keep on traversing until we reach the bottom left index and at that point if we have not yet found the taget val we simply return false;\n\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\n\n\n\tclass Solution {\n    public boolean searchMatrix(int[][] matrix, int target) {\n        \n        if(matrix.length == 0 || matrix[0].length == 0) return false;\n        \n        int col = matrix[0].length -1;\n        \n        int row = 0;\n        \n        \n        while( row < matrix.length && col >=0){\n            \n            int num = matrix[row][col];\n            \n            if(num == target) return true;\n            \n            else if( num > target){\n                col--;\n            }\n            else row++;\n        }\n        \n        \n        return false;\n        \n        \n    }}
[]