Search a 2D Matrix

Thought Process

The Search a 2D Matrix problem requires efficiently searching for a target value in a 2D matrix where each row is sorted, and the first element of each row is greater than the last element of the previous row. Here are two approaches:

Approach 1: Binary Search on Flattened Matrix - Treat the 2D matrix as a 1D array and apply binary search. Calculate the mid index in the 1D array and map it to the corresponding row and column in the 2D matrix using mid/col and mid%col. If the target is found, return true; otherwise, adjust the search range.

Approach 2: Two-Step Binary Search - First, perform binary search on the last column to identify the potential row where the target might exist. Then, perform binary search on the identified row to check if the target is present.

Approach 1: Binary Search on Flattened Matrix

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        
        int row = matrix.length;
        int col = matrix[0].length;

        // Assume our elements are stored in a 1D array and think of 
        // applying binary search on them.
        int left  = 0;
        int right = row*col-1;

        while(left<=right){

            int mid = (left+right)/2;
            
            // Corresponding row & col in matrix will be mid/col and mid%col
            int middleElement = matrix[mid/col][mid%col];

            if(target == middleElement)
                return true;

            else if(target > middleElement)
                left = mid+1;
            else
                right = mid-1;
        } 
        return false;
    }
}

Approach 2: Two-Step Binary Search

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        int row = matrix.length;
        int col = matrix[0].length;

        int up = 0;
        int down = row - 1;

        // Applying binary Search on last col (i.e. col-1), to get the desired row index.
        while (up <= down) {

            int mid = (up + down) / 2;

            if (matrix[mid][col - 1] == target)
                return true;

            else if (matrix[mid][col - 1] < target)
                up = mid + 1;
            else
                down = mid - 1;
        }
        if (up >= row)
            return false;

        // Now, applying binary search on the desired row.
        int idx = Arrays.binarySearch(matrix[up], target);
        if(idx<0)
            return false;
        else
            return true;
    }
}

Code Complexity

Time Complexity: O(log(m * n))

Both approaches use binary search, ensuring logarithmic time complexity with respect to the total number of elements in the matrix.

Space Complexity: O(1)

Both approaches use constant extra space, making them highly efficient.