Workspace

Problem workspace

3 day streakD

Search a 2D Matrix

MediumBinary SearchNumbers & matrices

The challenge

Determine whether the target exists in a rectangular matrix viewed in row-major order.

Each row is ascending and its first value is greater than the previous row’s last. Empty matrices return false. r × c fits a signed 32-bit index.

Example

[[1, 3, 5], [7, 9, 11]], target = 9 → true.

Use the walkthrough below to inspect the input and each state change.

See Flattened matrix search, step by step

Inspect the comparison, the invariant, and the next boundary.

Inclusive candidate indicestarget = 9
Matrix · row and column indices start at 0 · brackets show virtual indices
r / c012
01[0]3[1]5[2]
17[3]9[4]11[5]
Current comparisonResolved positionNumbers below = indices
Left
0
Middle
—
Right
5
Step 01 / 4

Start with the candidate indices

The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.

left = 0; right = 5

Recorded result so far

Not resolved
View exact input

Matrix: [[1,3,5],[7,9,11]] · target = 9

Put it into code

The matrix is globally sorted when read row by row. Search virtual indices without allocating a flattened copy.

Indices are zero-based. C++ uses C++17 or later.

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1
    while left <= right:
        mid = left + (right - left) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return True
        if value < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap