Google — Staircase Search in Row-Column Sorted Matrix

Problem (Google Favourite)

Given an m×n matrix where each row is sorted left→right and each column is sorted top→bottom, search for a target value. Return [row, col] or [-1, -1].

Example:

Matrix:        Target = 5
[1,  4,  7]
[2,  5,  8]
[3,  6,  9]
→ [1, 1]

Key Insight — Top-Right Corner

Start at the top-right corner:

If matrix[r][c] == target → found
If matrix[r][c] > target → go left (eliminate column)
If matrix[r][c] < target → go down (eliminate row)

Each step eliminates a row or column → O(m+n) total.

Solutions

Python

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

JavaScript

function searchMatrix(matrix, target) {
    let r = 0, c = matrix[0].length - 1;
    while (r < matrix.length && c >= 0) {
        if (matrix[r][c] === target) return [r, c];
        else if (matrix[r][c] > target) c--;
        else r++;
    }
    return [-1, -1];
}

Java

public int[] searchMatrix(int[][] m, int target) {
    int r=0, c=m[0].length-1;
    while (r<m.length && c>=0) {
        if (m[r][c]==target) return new int[]{r,c};
        else if (m[r][c]>target) c--;
        else r++;
    }
    return new int[]{-1,-1};
}

C++

vector<int> searchMatrix(vector<vector<int>>& m, int t) {
    int r=0, c=m[0].size()-1;
    while (r<(int)m.size() && c>=0) {
        if (m[r][c]==t) return {r,c};
        else if (m[r][c]>t) c--;
        else r++;
    }
    return {-1,-1};
}

C

void search(int** m, int rows, int cols, int t, int* r_out, int* c_out) {
    int r=0, c=cols-1;
    while (r<rows && c>=0) {
        if (m[r][c]==t){*r_out=r;*c_out=c;return;}
        else if (m[r][c]>t) c--;
        else r++;
    }
    *r_out=-1; *c_out=-1;
}

Complexity

Approach	Time	Space
Top-right	O(m+n)	O(1)
Naive	O(mn)	O(1)