Search a 2D Matrix II — Staircase Search O(m+n)

Problem 313 · Search a 2D Matrix II

Difficulty: Medium · Pattern: Staircase Search (not pure BS)

Rows sorted L→R, columns sorted T→B (not globally sorted). Find target.

Intuition

Start at top-right: if value > target, move left; if < target, move down. Each step eliminates a row or column.

Solutions

# Python
def searchMatrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    r, c = 0, n-1
    while r < m and c >= 0:
        if matrix[r][c] == target: return True
        elif matrix[r][c] > target: c -= 1
        else: r += 1
    return False

// Java
public boolean searchMatrix(int[][] matrix, int target) {
    int r=0, c=matrix[0].length-1;
    while (r<matrix.length&&c>=0) {
        if (matrix[r][c]==target) return true;
        else if (matrix[r][c]>target) c--; else r++;
    }
    return false;
}

// C++
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int r=0, c=matrix[0].size()-1;
    while (r<(int)matrix.size()&&c>=0) {
        if (matrix[r][c]==target) return true;
        else if (matrix[r][c]>target) c--; else r++;
    }
    return false;
}

Complexity

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