Search a 2D Matrix — InterviewPrepKit

Solving tips

Spot that the two ordering guarantees make the matrix one flat sorted array of length m*n read row by row, so a single binary search applies.
Map a flat index k to a cell with matrix[k // n][k % n] (divide by number of COLUMNS n) instead of materializing the array; run textbook binary search over 0..m*n-1.
Target O(log(m*n)) time, O(1) space; the two-search version (find row, then search within) is O(log m + log n) which is the same bound.
Common pitfall: swapping // and % in the index conversion, or confusing this with Search a 2D Matrix II (sorted rows AND columns but no cross-row chaining), which needs a staircase walk instead.

Problem

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

Each row is sorted in ascending order.
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

Hint 1

Only one row can possibly contain the target. Which property of the matrix tells you which row that is?

Hint 2

Two binary searches work: first over rows (compare the target against each row's first and last elements), then a standard binary search inside the chosen row. That's O(log m + log n) = O(log(m·n)).

Hint 3

You can also do it with a single binary search: treat the matrix as one flat sorted array of length `m * n`, and convert a flat index `k` to coordinates with `row = k // n`, `col = k % n`.

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


class Solution:
    def searchMatrix(self, 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 runs fine — but the problem explicitly demands O(log(m·n)), and the brute force ignores both sortedness guarantees entirely.

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

The insight: 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 is the classical divide-and-conquer technique that locates a value in a sorted sequence in O(log n) by halving the interval each step.

from typing import List


class Solution:
    def searchMatrix(self, 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:

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.
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 insight: 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]. So run one textbook binary search over indices 0 .. m·n - 1.

from typing import List


class Solution:
    def searchMatrix(self, 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):

lo	hi	mid	cell	value	action
0	11	5	(1,1)	11	11 < 13 → lo = 6
6	11	8	(2,0)	23	23 > 13 → hi = 7
6	7	6	(1,2)	16	16 > 13 → hi = 5

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

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

Both approaches meet the bound (log m + log n is log(m·n)); the flattened version is fewer lines and one loop, the two-phase version generalizes better when rows only guarantee “sorted rows” without 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 doesn’t care what shape your data is stored in — it only needs random access to a conceptually sorted sequence. When a 2D (or k-D) structure has a global order, map indices instead of copying data: k // n and k % n give you a virtual flat array for free.