Search a 2D Matrix

A matrix looks like a two-dimensional problem, and candidates often reach for two nested searches or a walk across the grid. For this matrix, that is overthinking it. If you read it the way you read a page — left to right, then the next line — the values come out in sorted order. So it is one sorted list, and one binary search is enough.

The only real work is the index arithmetic, and that is exactly what the interviewer is watching.

The problem

You are given a matrix with m rows and n columns. Each row is sorted in increasing order, and the first value of each row is greater than the last value of the row above. Given a target, return whether it appears in the matrix.

matrix = [[ 1,  3,  5,  7],          [10, 11, 16, 20],          [23, 30, 34, 60]]

• target = 11 → True. It is in row 1, column 1.
• target = 13 → False. It would sit between 11 and 16, but it is not there.

Constraints: 1 ≤ m, n ≤ 100, values between -10⁴ and 10⁴, and the solution should run in O(log(m × n)).

Clarifying questions

• Do all rows have the same length? Yes, it is a proper rectangle.
• Is "first of a row is greater than last of the previous row" guaranteed? Yes. Without it the problem is different (see the follow-ups).
• Can the matrix or a row be empty? Not by the constraints, but the code should return False rather than crash.
• Return a position or just yes/no? Just yes/no.

Approach 1: the simple way

Check every cell.

def search_matrix_scan(matrix: list[list[int]], target: int) -> bool:    """Check every cell: O(rows * cols)."""    return any(value == target for row in matrix for value in row)

Time: O(m × n). Space: O(1).

At 100 × 100 that is 10,000 comparisons, which runs fast. But it ignores every guarantee the problem gives you, and the interviewer asked for O(log(m × n)): about 14 comparisons here. On a 10,000 × 10,000 matrix, the scan is 10⁸ steps per query and binary search is 27.

A smarter scan checks the last value of each row to pick the row, then scans that row: O(m + n). Better, but still not logarithmic.

The key insight

Read the matrix row by row and write the values in one line:

flat index:  0  1  2  3   4   5   6   7   8   9  10  11value:       1  3  5  7  10  11  16  20  23  30  34  60

Each row is sorted, and each row starts above where the last one ended, so this line is sorted. You can binary search it over the flat indices 0 to m × n - 1. You never build the line; you convert each flat index back to a cell when you need its value.

Derive the conversion instead of recalling it. Each row holds n values (n = number of columns). Flat indices 0 to n - 1 are row 0, n to 2n - 1 are row 1, and so on. So flat index k is in row k // n, and the column is what is left over: k % n. Check it on the example, where n = 4: flat index 6 is row 6 // 4 = 1, column 6 % 4 = 2, which holds 16. Counting by hand, row 0 holds flat indices 0–3 and row 1 holds 4–7, so index 6 is the third value of row 1: 16. Correct.

Note what you divide by: the number of columns, not rows. On a square matrix both give the same answer, which is why the wrong one survives testing.

Approach 2: binary search over flat indices

1def search_matrix(matrix: list[list[int]], target: int) -> bool:2    """Binary search the matrix as one sorted list of rows * cols values."""3    if not matrix or not matrix[0]:4        return False5    rows, cols = len(matrix), len(matrix[0])6    left, right = 0, rows * cols - 17    while left <= right:8        mid = left + (right - left) // 29        value = matrix[mid // cols][mid % cols]      # flat index -> (row, column)10        if value == target:11            return True12        if value < target:13            left = mid + 114        else:15            right = mid - 116    return False

This is the exact-match template from the core lesson with one changed line: how you read the value at mid.

For target 11, the first probe is flat index (0 + 11) // 2 = 5, which is row 1, column 1, which holds 11. Found in one step.

Dry run for target 13 (missing):

Three probes out of twelve cells. Step 2 jumps straight into the last row and rules out the whole row with one look.

Time: O(log(m × n)), which equals O(log m + log n). At 100 × 100, at most 14 probes. Space: O(1): no flattened copy is ever made.

A second, equally fast way is two searches: first binary search the first column to find the last row whose first value is at most the target, then binary search that row. It is also O(log m + log n). It is more code with two loops to get right, so the flat version is usually the better one to write. Mention the other if the interviewer asks for alternatives.

Here is what each method costs on a 100 × 100 matrix, in the worst case:

The guarantee that each row starts above where the previous one ended is what buys the drop from hundreds to 14. When an interviewer removes it, the usual answer falls back to the staircase.

Edge cases

• Empty matrix or empty rows: the guard returns False before computing rows * cols - 1 = -1.
• One row: mid // cols is always 0; it is ordinary binary search.
• One column: cols = 1, so mid // 1 = mid and mid % 1 = 0; binary search down the column.
• Non-square matrix: the case that catches mid // rows. Test a 3 × 4 and a 4 × 3 matrix.
• Target smaller than matrix[0][0] or larger than the last cell: the range empties at one end; no special check is needed.

Follow-ups

• "Now each row is sorted and each column is sorted, but rows may overlap." The flat list is no longer sorted, so this method fails. Start at the top-right corner: if the value is too big, the whole column below is too big, so move left; if too small, the whole row to the left is too small, so move down. Each step removes a row or a column, so it is O(m + n):

1def search_matrix_staircase(matrix: list[list[int]], target: int) -> bool:2    """Rows and columns sorted separately: walk from the top-right corner."""3    if not matrix or not matrix[0]:4        return False5    row, col = 0, len(matrix[0]) - 16    while row < len(matrix) and col >= 0:7        value = matrix[row][col]8        if value == target:9            return True10        if value > target:11            col -= 1                         # everything below in this column is bigger too12        else:13            row += 1                         # everything left in this row is smaller too14    return False

• "Return the position." Return (mid // cols, mid % cols) instead of True.
• "Find the k-th smallest value in a row-and-column sorted matrix." Binary search on the value, and for each candidate count how many cells are at most it, using the same staircase walk. That is binary search on the answer, covered in Koko Eating Bananas.