Rows and columns are each sorted ascending, but without the “whole matrix is one sorted sequence” guarantee (a row’s first element isn’t necessarily greater than the previous row’s last). (LeetCode problem)
Brute force: O(n×m). Better: binary search each row individually — O(n log m).
Optimal: start at the top-right corner. If the current cell equals the target, done. If it’s smaller, the whole current column above is too small, so move down a row. If it’s larger, the whole current row to the right is too large, so move left a column. This eliminates a full row or column each step.
class Solution { public int[] searchMatrix(int[][] matrix, int target) { int row = 0, col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) { if (matrix[row][col] == target) { return new int[]{row, col}; } else if (matrix[row][col] < target) { row++; } else { col--; } } return new int[]{-1, -1}; }}Time: O(n + m).