Search a 2D Matrix II

Problem Statement

Given an m x n matrix sorted in ascending order along each row and each column, return true if target exists.

Example

Input:  target = 5 in a row- and column-sorted matrix
Output: true

Approach (Search-Space Elimination)

Here rows and columns are sorted independently, so simple flattening does not apply. Start at the top-right corner. If the value equals the target, done. If it is larger, move left (drop that column); if smaller, move down (drop that row). Each step removes a full row or column.

Complexity

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

Solution Code

Python

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False

Java

boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0 || matrix[0].length == 0) return false;
    int row = 0, col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] > target) col--;
        else row++;
    }
    return false;
}

C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;
    int row = 0, col = (int)matrix[0].size() - 1;
    while (row < (int)matrix.size() && col >= 0) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] > target) col--;
        else row++;
    }
    return false;
}

Key Takeaways

• The top-right (or bottom-left) corner is special: one direction increases, the other decreases.
• This is search-space elimination, the sibling idea behind binary search.
• Reference: LeetCode 240 (Search a 2D Matrix II).