Search a 2D Matrix

Problem

You are given an m x n integer matrix with two ordering guarantees:

1. Each row is sorted in ascending order.
2. The first value of each row is strictly greater than the last value of the previous row.

Together these mean the whole matrix, read row by row, is one sorted sequence. Given a target integer, return True if it appears in the matrix and False otherwise. The expected solution runs in O(log(m * n)) time.

Examples

• matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 → True 3 is in row 0 ([1,3,5,7]).
• matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 → False 13 falls between 11 and 16 in reading order but is not present.
• matrix = [[1]], target = 2 → False A 1×1 matrix without the target.

Constraints

• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4
• Required time: O(log(m * n)) — a full scan is not the intended answer.

Think about it first

TL;DR

One binary search over the matrix viewed as a flat sorted array — O(log(m·n)) time, O(1) space.

Approach 1 — Brute force

Scan every cell and compare against the target.

from typing import List


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

• Time: O(m·n). Space: O(1).

At m = n = 100 this is only 10^4 cells, so it works within limits, but the problem requires O(log(m·n)) and this ignores both sortedness guarantees.

Approach 2 — Two binary searches (row, then column)

The “first element of each row exceeds the last of the previous row” guarantee means the target can live in exactly one row: the row whose first element is <= target. Binary search the rows for that boundary, then binary search within the row.

Binary search locates a value in a sorted sequence in O(log n) by halving the interval each step.

from typing import List


def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])

    # Find the last row whose first element is <= target.
    top, bottom = 0, m - 1
    while top <= bottom:
        mid = (top + bottom) // 2
        if matrix[mid][0] > target:
            bottom = mid - 1
        else:
            top = mid + 1
    row = bottom  # candidate row (may be -1 if target < everything)
    if row < 0:
        return False

    lo, hi = 0, n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if matrix[row][mid] == target:
            return True
        if matrix[row][mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

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

1. Row search: mid = 1, matrix[1][0] = 10 > 3 → bottom = 0. Then mid = 0, matrix[0][0] = 1 <= 3 → top = 1. Loop ends with bottom = 0, so row = 0.
2. Column search in [1,3,5,7]: mid = 1 gives 3 == 3 → True.

• Time: O(log m + log n) = O(log(m·n)). Space: O(1).

Approach 3 — Single binary search on the flattened matrix

The two guarantees make the matrix, read left-to-right top-to-bottom, one sorted array of length m·n. There is no need to materialize it: flat index k maps to matrix[k // n][k % n]. Run one binary search over indices 0 .. m·n - 1.

from typing import List


def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        value = matrix[mid // n][mid % n]
        if value == target:
            return True
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Walkthrough with the same matrix and target = 13 (m = 3, n = 4, indices 0–11):

Now lo > hi, so return False — 13 is absent, as expected.

• Time: O(log(m·n)). Space: O(1).

Both approaches meet the bound, since log m + log n equals log(m·n). The flattened version is fewer lines and a single loop; the two-phase version generalizes better when rows are sorted but lack the cross-row ordering.

Common pitfalls

• Mixing up // and % in the flat-to-2D conversion — it is row = mid // n (divide by the number of columns), col = mid % n.
• Forgetting the row < 0 case in the two-search version when the target is smaller than matrix[0][0].
• Using this problem’s approach on Search a 2D Matrix II, where rows and columns are sorted but rows don’t chain — that variant needs the staircase walk from a corner, not a flat binary search.
• Off-by-one in the row search: you want the last row with first <= target, which is bottom after a while top <= bottom loop, not top.

Pattern takeaway

Binary search only needs random access to a conceptually sorted sequence, regardless of how the data is stored. When a 2D (or k-D) structure has a global order, map indices instead of copying data: k // n and k % n give a virtual flat array without extra space.