Search a 2D Matrix: the idea to remember.

The core insight

Treat the matrix as one sorted array; map an index using division and remainder.

Why it works

Global row ordering makes the flattened sequence sorted, so ordinary binary search applies.

The mistake to avoid

Flattening is invalid when only individual rows and columns are sorted.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0 || matrix[0].length == 0) return false;
    int cols = matrix[0].length;
    int left = 0, right = matrix.length * cols - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int value = matrix[mid / cols][mid % cols];
        if (value == target) return true;
        if (value < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

Make the next connection