Search 2d Matrix

74.Search a 2D Matrix

Matrix

Binary Search

Two Pointers

Problem Statement:

Write an efficient algorithm that searches for a value target in an m x n matrix. The matrix has the following properties: - Integers in each row are sorted from left to right - The first element of each row is greater than the last element of the previous row

Example:

Input:

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

→

Output:

true

Algorithm:

1. Solution 1: Use binary search treating matrix as 1D array
2. Solution 2: Start from top-right, move left/down
3. Handle edge cases like empty matrix
4. Convert 1D index to 2D using division/modulo

Complexity:

Binary Search: O(log(mn)) | Linear Search: O(m + n)

Java Solution:

// Binary Search Solution - O(log(mn))
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    if (m == 0) return false;
    int n = matrix[0].length;
    
    // Treat matrix as sorted 1D array
    int left = 0, right = m * n - 1;
    
    while (left <= right) {
        int pivot = (left + right) / 2;
        // Convert to 2D indices
        int element = matrix[pivot / n][pivot % n];
        
        if (target == element) return true;
        else if (target < element) right = pivot - 1;
        else left = pivot + 1;
    }
    return false;
}

// Linear Search Solution - O(m + n)
public boolean searchMatrixMN(int[][] matrix, int target) {
    if (matrix.length == 0) return false;
    
    // Start from top-right corner
    int row = 0;
    int col = matrix[0].length - 1;
    
    while (row < matrix.length && col >= 0) {
        if (target < matrix[row][col]) 
            col--;  // Move left if target is smaller
        else if (target > matrix[row][col])
            row++;  // Move down if target is larger
        else 
            return true;
    }
    
    return false;
}

Python Solution:

# Binary Search Solution
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    if not matrix: return False
    m, n = len(matrix), len(matrix[0])
    
    left, right = 0, m * n - 1
    
    while left <= right:
        pivot = (left + right) // 2
        element = matrix[pivot // n][pivot % n]
        
        if target == element:
            return True
        elif target < element:
            right = pivot - 1
        else:
            left = pivot + 1
            
    return False

# Linear Search Solution
def searchMatrixMN(self, matrix: List[List[int]], target: int) -> bool:
    if not matrix: return False
    
    row, col = 0, len(matrix[0]) - 1
    
    while row < len(matrix) and col >= 0:
        if target < matrix[row][col]:
            col -= 1  # Move left
        elif target > matrix[row][col]:
            row += 1  # Move down
        else:
            return True
            
    return False

C++ Solution:

// Binary Search Solution
bool searchMatrix(vectorint>>& matrix, int target) {
    int m = matrix.size();
    if (m == 0) return false;
    int n = matrix[0].size();
    
    int left = 0, right = m * n - 1;
    
    while (left <= right) {
        int pivot = left + (right - left) / 2;
        int element = matrix[pivot / n][pivot % n];
        
        if (target == element) return true;
        else if (target < element) right = pivot - 1;
        else left = pivot + 1;
    }
    return false;
}

// Linear Search Solution
bool searchMatrixMN(vectorint>>& matrix, int target) {
    if (matrix.empty()) return false;
    
    int row = 0;
    int col = matrix[0].size() - 1;
    
    while (row < matrix.size() && col >= 0) {
        if (target < matrix[row][col])
            col--;  // Move left
        else if (target > matrix[row][col])
            row++;  // Move down
        else
            return true;
    }
    return false;
}