Matrix Search

Row-Col Sorted (Staircase)

When each row and each column is sorted independently: start at the top-right corner. If the target is smaller, move left (eliminate column). If larger, move down (eliminate row). O(m+n) steps.

O(m*n)

O(n)

How It Works

In a matrix where every row and every column is independently sorted, the top-right corner is special: it is the largest value in its row and the smallest in its column. Compare it to the target. If the corner value is bigger, the entire rightmost column can be discarded, so move left. If it is smaller, the entire top row can be discarded, so move down. Repeat from the new corner of the shrunken submatrix.

Each comparison permanently eliminates a full row or column, so the walk takes at most m + n steps — O(m+n) time with O(1) space. That beats scanning all m*n cells and also beats binary searching every row when the matrix is roughly square. The same logic works starting from the bottom-left corner; the two corners where row order and column order disagree are the valid starting points.

Step-by-Step Visualization

Search for 5 in row-col sorted matrix

Position(0,2) = 7

Target5

1/3

Code

Java

static boolean searchMatrix(int[][] matrix, int target) {
  int row = 0, col = matrix[0].length - 1;

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

// Example: search for 5 in row-col sorted matrix

Tips & Gotchas

1Start from top-right (or bottom-left) corner

2If current > target, move left. If current < target, move down

3Eliminates one row or column with each comparison

Practice Problems

1Search a 2D Matrix II
2Count Negative Numbers in a Sorted Matrix
3Leftmost Column with at Least a One

About the Matrix Search Pattern

Find a target value in a matrix with some sorted property. The sorting enables techniques faster than scanning every cell.

Key insight

For traversal: use direction arrays dx=[0,0,1,-1], dy=[1,-1,0,0]. For sorted matrix search, start from top-right corner. For grid DP, fill row by row — current cell depends on top and left.

Common Matrix Interview Problems

Spiral Matrix
Rotate Image
Search a 2D Matrix
Number of Islands
Maximal Square
Set Matrix Zeroes
Word Search

Frequently Asked Questions

Why must the search start at the top-right or bottom-left corner?

Those corners give an unambiguous decision: at the top-right, moving left always decreases the value and moving down always increases it. At the top-left or bottom-right, both available moves change the value in the same direction, so a comparison there cannot tell you which way to go.

Could binary search do better than O(m+n) here?

For a single lookup in an n x n matrix, O(m+n) is essentially optimal — an adversary argument shows any correct algorithm must examine a cell on each anti-diagonal. Per-row binary search costs O(m log n), which is worse for square matrices, though it can win when the matrix is extremely wide and short.