---
title: "Matrix search (sorted grid)"
url: https://algopath.pro/patterns/matrix-search
language: en
summary: "In a grid sorted both ways, one corner can only move in a single direction. Each comparison drops a whole row or column."
updated: 2026-08-24
---

# Matrix search (sorted grid)

In a grid sorted both ways, one corner can only move in a single direction. Each comparison drops a whole row or column.

## How does Matrix search (sorted grid) work?

There are two kinds of sorted grid. In one each row continues the previous, in the other rows and columns merely rise.

The first kind is a sorted list folded into rows. Binary search over r times c positions.

For the second kind, start at the top-right corner. Everything to its left is smaller and everything below is larger.

If the value there is too large, move left. That drops the whole column at once.

If it is too small, move down. That drops the whole row.

Every step removes one row or one column. So the walk ends within r plus c steps.

- `start at 7, top right` Looking for 5 in a grid that rises both ways.
- `7 is too large` Everything below 7 in that column is larger. Move left.
- `4 is too small` Everything left of 4 in that row is smaller. Move down.
- `now at 5` The value under the walk matches the target.
- `three steps` Nine cells, three comparisons. Two lines were dropped whole.

## When should you use Matrix search (sorted grid)?

- matrix sorted along both rows and columns
- search for a value in a 2D sorted grid
- start from a corner and eliminate a row or column
- row and column both monotonic

## What is Matrix search (sorted grid) confused with?

- **Binary search (array)** - When each row continues the last, the grid is one sorted list. A plain binary search then works.
- **Two pointers (opposite ends)** - The staircase walk is that idea in two dimensions. Exactly one index moves per step.
- **Matrix traversal (spiral / diagonal)** - That visits every cell in a chosen order. Here most cells are never read at all.
- **Linear search** - A scan works and costs O(rc). The sorted structure is what makes it wasteful.

## What is the time and space complexity of Matrix search (sorted grid)?

An r by c grid gives O(r + c) for the staircase walk. A fully sorted grid allows O(log rc).

## A worked example of Matrix search (sorted grid)

### The kth smallest value in a sorted grid

A grid has rows and columns that both rise. Return its kth smallest value.

Flattening and sorting works, but it reads every cell.

Binary search over the range of values, not over the positions.

For a candidate value, count how many cells are not larger. That count says which half to keep.

```javascript
function kthSmallest(matrix, k) {
    const n = matrix.length;
    let lo = matrix[0][0];
    let hi = matrix[n - 1][n - 1];

    const countNotAbove = (value) => {
        let count = 0;
        let row = n - 1;

        // one staircase walk, starting from the bottom-left corner
        for (let col = 0; col < n; col++) {
            while (row >= 0 && matrix[row][col] > value) row--;
            count += row + 1;
        }

        return count;
    };

    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (countNotAbove(mid) >= k) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}
```

## Common mistakes with Matrix search (sorted grid)

- **Starting from the wrong corner** The top-left cell is smaller than both neighbours, so it gives no direction. Start top-right or bottom-left.
- **Treating a row-wise grid as fully sorted** Searching by position needs each row to continue the last. Check that before flattening.
- **Sorting the whole grid** That throws away the structure you were handed. It also costs rc log rc.
- **Returning the middle candidate** In a value search the answer must be a value that exists. Squeeze until the bounds meet.

## Which interview problems use Matrix search (sorted grid)?

- **Search a 2D matrix** One sorted list folded into rows.
- **Search a 2D matrix II** The staircase walk from a corner.
- **Kth smallest in a sorted matrix** Binary search over values, counting per candidate.
- **Find a peak element II** Binary search over the columns.
- **Count negative numbers in a sorted matrix** The same staircase, counting instead of matching.
- **Median of a row-wise sorted matrix** Count how many cells are not above a candidate.
- **Smallest common element in all rows** One pointer per row, moved together.

## JavaScript

```javascript
function searchMatrix(matrix, target) {
    let row = 0;
    let col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        const v = matrix[row][col];
        if (v === target) return true;
        if (v > target) col--;
        else row++;
    }
    return false;
}
```

## Python

```python
def search_matrix(matrix, target):
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        v = matrix[row][col]
        if v == target:
            return True
        if v > target:
            col -= 1
        else:
            row += 1
    return False
```

## PHP

```php
function searchMatrix(array $matrix, int $target): bool {
    $row = 0;
    $col = count($matrix[0]) - 1;
    while ($row < count($matrix) && $col >= 0) {
        $v = $matrix[$row][$col];
        if ($v === $target) return true;
        if ($v > $target) $col--;
        else $row++;
    }
    return false;
}
```