74. Search a 2D Matrix

Intitution

We can treat the entire matrix as a flattened 1D sorted array because of its properties:

• Each row is sorted

• Each row starts with a number greater than the previous row’s last element

But instead of flattening, we perform binary search first on rows, then on the selected row.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{N}*\log{M})$

Code

// Helper function to find the potential row where the target could be present
int[] binarySearchOnFirstColumn(int[][] matrix, int target, int totalRows, int lastColIndex) {
    int left = 0, right = totalRows - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        // If first element of mid-row is equal to target
        if (matrix[mid][0] == target) {
            return matrix[mid];
        }

        // Check if the target lies between previous row's end and this row's start
        if ((mid - 1 < 0 || matrix[mid - 1][lastColIndex] < target) &&
            (matrix[mid][0] <= target && matrix[mid][lastColIndex] >= target)) {
            return matrix[mid];
        }

        if (matrix[mid][0] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    // If not found, return the most likely candidate row
    return matrix[Math.min(left, totalRows - 1)];
}

public boolean searchMatrix(int[][] matrix, int target) {
    int totalRows = matrix.length;
    int totalCols = matrix[0].length;

    // Step 1: Find the right row using binary search
    int[] potentialRow = binarySearchOnFirstColumn(matrix, target, totalRows, totalCols - 1);

    // Step 2: Perform binary search within the identified row
    int index = Arrays.binarySearch(potentialRow, target);
    return index >= 0;
}