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.

Sources: Wikipedia: Binary search

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

function searchMatrix(matrix: number[][], target: number): boolean {
    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;
}

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

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

    public static boolean searchMatrix(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            int v = matrix[row][col];
            if (v == target) return true;
            if (v > target) col--;
            else row++;
        }
        return false;
    }

    public static bool SearchMatrix(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].Length - 1;
        while (row < matrix.Length && col >= 0) {
            int 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)?

Use Matrix search (sorted grid) when the problem statement says “matrix sorted along both rows and columns”, “search for a value in a 2D sorted grid” or “start from a corner and eliminate a row or column”. A solution built on it usually runs in O(m+n).

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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Matrix search (sorted grid) confused with?

Matrix search (sorted grid) is most often confused with Binary search (array), Two pointers (opposite ends), Matrix traversal (spiral / diagonal) and Linear search.

• 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)?

Interview problems solved with Matrix search (sorted grid) include Search a 2D matrix, Search a 2D matrix II, Kth smallest in a sorted matrix, Find a peak element II, Count negative numbers in a sorted matrix, Median of a row-wise sorted matrix and Smallest common element in all rows.

• 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)?

The target complexity of Matrix search (sorted grid) is O(m+n).

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