Search 2d Matrix II

240.Search a 2D Matrix II

Matrix

Two Pointers

Divide and Conquer

Problem Statement:

Write an efficient algorithm that searches for a value target in an m x n matrix. This 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

Example:

Input:

matrix = [ [1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17] ]
target = 5

→

Output:

true

Algorithm:

1. Start from top-right corner
2. If target smaller, go left (decreasing values)
3. If target larger, go down (increasing values)
4. Continue until found or out of bounds

Complexity:

Time: O(m + n) | Space: O(1)

Java Solution:

public boolean searchMatrix(int[][] matrix, int target) {
    // Handle empty matrix
    if (matrix.length == 0) return false;
    
    // Start from top-right corner
    int row = 0;
    int col = matrix[0].length - 1;
    
    // Move left or down until target found or out of bounds
    while (row < matrix.length && col >= 0) {
        if (target < matrix[row][col])
            col--;  // Target is smaller, go left
        else if (target > matrix[row][col])
            row++;  // Target is larger, go down
        else
            return true;  // Target found
    }
    
    return false;
}

Python Solution:

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    # Handle empty matrix
    if not matrix:
        return False
    
    # Start from top-right corner
    row, col = 0, len(matrix[0]) - 1
    
    # Move left or down until target found or out of bounds
    while row < len(matrix) and col >= 0:
        if target < matrix[row][col]:
            col -= 1  # Target is smaller, go left
        elif target > matrix[row][col]:
            row += 1  # Target is larger, go down
        else:
            return True  # Target found
            
    return False

C++ Solution:

bool searchMatrix(vectorint>>& matrix, int target) {
    // Handle empty matrix
    if (matrix.empty()) return false;
    
    // Start from top-right corner
    int row = 0;
    int col = matrix[0].size() - 1;
    
    // Move left or down until target found or out of bounds
    while (row < matrix.size() && col >= 0) {
        if (target < matrix[row][col])
            col--;  // Target is smaller, go left
        else if (target > matrix[row][col])
            row++;  // Target is larger, go down
        else
            return true;  // Target found
    }
    
    return false;
}