Matrix search (sorted grid)

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.

1. start at 7, top rightLooking for 5 in a grid that rises both ways.
2. 7 is too largeEverything below 7 in that column is larger. Move left.
3. 4 is too smallEverything left of 4 in that row is smaller. Move down.
4. now at 5The value under the walk matches the target.
5. three stepsNine cells, three comparisons. Two lines were dropped whole.

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;
}

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.

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;
}

When should you use Matrix search (sorted grid)?

These phrases in a problem statement point here:

• •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.

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.

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

O(m+n)

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