Search a 2D Matrix

35 min · searchMatrix()

A grid with the right ordering is really one long sorted list wearing rows and columns.

You're given an m x n integer matrix and a target. Each row rises from left to right, and the first value of every row is greater than the last value of the row above it. Return true when target appears in the matrix and false otherwise.

If you flatten the matrix — read each row from left to right, top to bottom — the result is one strictly increasing sequence. You don't need to build that sequence.

A few ground rules:

Every row has the same number of columns.
The matrix contains at least one cell.
Use the global ordering, not a full cell-by-cell scan.

Constraints

1 <= m, n <= 300
-1_000_000 <= matrix[row][col], target <= 1_000_000
Each row is strictly increasing.
The first value of each row is greater than the last value of the previous row.

Hints

Number the cells

Pretend the matrix has indices from 0 through m * n - 1, exactly like a flat array. Binary search can work on those virtual indices.

Translate an index

For a virtual index middle, its row is middle // n and its column is middle % n.

Keep the matrix intact

Compare matrix[middle // n][middle % n] with target, then discard half of the virtual index range just as you would for a one-dimensional array.

Follow-up

What changes if every row and column is sorted, but a row's first value no longer has to be greater than the previous row's last value?

Visible cases

Examples

Example 1

ready

Input: matrix = [ [ 1, 4, 7 ], [ 10, 13, 18 ] ] target = 13
Expected: true
Why: 13 appears in the second row

Example 2

ready

Input: matrix = [ [ -8, -3, 0 ], [ 5, 9, 14 ] ] target = 6
Expected: false
Why: 6 falls between two stored values

Example 3

ready

Input: matrix = [ [ 42 ] ] target = 42
Expected: true
Why: a one-cell matrix can still contain the target

Interview signal

Asked at

AmazonMicrosoftAdobe

Scan every cell

Visit the rows in order and compare every value with target.

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    for row in matrix:
        for value in row:
            if value == target:
                return True
    return False

Time O(mn). Space O(1). The scan can touch all m * n cells.

Virtual flattened search

The row boundary doesn't break the ordering: the last value of one row is smaller than the first value of the next. Number the cells as though they formed one array of length m * n.

For any virtual index middle:

middle // columns gives its row.
middle % columns gives its column.

That translation lets binary search read the middle cell without copying the matrix.

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    rows, columns = len(matrix), len(matrix[0])
    left, right = 0, rows * columns - 1
 
    while left <= right:
        middle = left + (right - left) // 2
        value = matrix[middle // columns][middle % columns]
        if value == target:
            return True
        if value < target:
            left = middle + 1
        else:
            right = middle - 1
 
    return False

The useful move is the virtual view: reshape the indices, not the data.

Time O(log(mn)). Space O(1). Each comparison halves the virtual range, and the matrix stays where it is.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraymatrix: int[][] · target: int

Expected

true

Run: visible + custom · Submit: full suite