74. Search a 2D Matrix

Description

Given a m x n matrix and a target number, the task is to determine if the target exists in the matrix. The matrix has the following properties:

• Integers in each row are sorted in ascending order from left to right.
• Integers in each column are sorted in ascending order from top to bottom.

Intuition

To efficiently find the target in the matrix, we can leverage its sorted properties. By performing binary searches, we can narrow down the potential rows and columns where the target might be located.

Approach

1. First Binary Search: - Perform a binary search on the first column of the matrix to identify the row in which the target could potentially exist. - Initialize two pointers left and right to the first and last rows, respectively. - Calculate the middle row (mid) and check if the target lies between the first and last elements of this row. - If it does, narrow down to this row for further searching. - If the target is less than the first element of the middle row, adjust the right pointer to mid - 1. - If the target is greater than the last element of the middle row, adjust the left pointer to mid + 1.
2. Second Binary Search: - Once the correct row is identified, perform a binary search within this row. - Adjust left and right pointers to the start and end of the columns of the identified row. - Calculate the middle column (mid) and compare its value with the target. - If the value at mid equals the target, return True. - If the target is less than the value at mid, adjust the right pointer to mid - 1. - If the target is greater than the value at mid, adjust the left pointer to mid + 1.
3. Return Result: - If the target is not found within the identified row, return False.

Complexity

Time Complexity:

O(log(m) + log(n)) = O(log(mn)), where m is the number of rows and n is the number of columns. This is because we perform binary search twice, first on the rows and then on the columns.

Space Complexity:

O(1), as we use a constant amount of extra space.

Code

C++

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        int left = 0; 
        int right = matrix.size() - 1;
        int index = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[mid][0] <= target && matrix[mid][matrix[mid].size() - 1] >= target) {
                left = 0;
                right = matrix[mid].size() - 1;
                index = mid;
                break;
            }
            if (matrix[mid][0] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (index == -1) {
            return false;
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[index][mid] == target) {
                return true;
            }
            if (matrix[index][mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};

Python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        left = 0
        right = len(matrix) - 1
        index = -1

        # First binary search to find the correct row
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[mid][0] <= target <= matrix[mid][-1]:
                left = 0
                right = len(matrix[mid]) - 1
                index = mid
                break
            elif matrix[mid][0] < target:
                left = mid + 1
            else:
                right = mid - 1
                
        if index == -1:
            return False
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[index][mid] == target:
                return True
            elif matrix[index][mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0; 
        int right = matrix.length - 1;
        int index = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[mid][0] <= target && matrix[mid][matrix[mid].length - 1] >= target) {
                left = 0;
                right = matrix[mid].length - 1;
                index = mid;
                break;
            }
            if (matrix[mid][0] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // If no valid row is found, return false
        if (index == -1) {
            return false;
        }
        // Second binary search within the identified row
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[index][mid] == target) {
                return true;
            }
            if (matrix[index][mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

JavaScript

var searchMatrix = function(matrix, target) {
    let left = 0; 
    let right = matrix.length-1;
    let index = -1;

    while( left <= right ){
        let mid = Math.floor( ( left + right ) / 2 );
        if( matrix[mid][0] <= target  && matrix[mid][matrix[mid].length-1] >= target ){
            left = 0;
            right = matrix[mid].length-1;
            index = mid
            break
        }
        if( matrix[mid][0] < target ){
            left  = mid+1
        }else{
            right = mid-1
        }
    }
    while(left <= right ){
        let mid = Math.floor(( left + right ) / 2 );
        if( matrix[index][mid] == target ){
            return true 
        }
        if( matrix[index][mid] < target ){
            left  = mid+1
        }else{
            right = mid-1
        }
    }
    return false
};