publicbooleansearchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0) { returnfalse; } introw= matrix.length, col = matrix[0].length; for (intr=0; r < row; ++r) { for (intc=0; c < col; ++c) { if (matrix[r][c] == target) { returntrue; } } } returnfalse; }

Time: $O(MN)$ Space: $O(1)$

Starting From Corner

Note:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

publicbooleansearchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { returnfalse; } introw= matrix.length, col = matrix[0].length; intr=0, c = col - 1; while (r < row && c >= 0) { if (matrix[r][c] == target) returntrue; if (target < matrix[r][c]) { // go left c -= 1; } else { // go down r += 1; } } returnfalse; }

Time: $O(M + N)$ Space: $O(1)$

Binary Search

Learn the conversion between matrix indices and its corresponding listâ€™s index.