← DSA Atlas
Dedicated problem page · #74

Search a 2D Matrix

MediumBinary SearchBinary search on a flattened gridBinary search
Solve on LeetCode ↗
74
MediumBinary SearchBinary searchBinary search on a flattened grid

Search a 2D Matrix

Given an m x n integer matrix where every row is sorted left to right and the first integer of each row is greater than the last integer of the previous row, decide whether a target value appears in the matrix. Return true if it does, otherwise false.

Open official problem prompt ↗
In plain English

Report whether a target integer exists anywhere in a matrix that is sorted as if its rows were laid end to end.

Picture it like this

Think of a multi-page dictionary where every page continues alphabetically from the previous one. You can binary-search a global page-and-line position instead of scanning page by page.

Example
Input
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output
true
Why
3 sits in the first row at column 1, so the target is present.
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
Pattern lesson

See the pattern, then code

Binary search on a flattened grid
Recognition clue

The two ordering guarantees (rows sorted, and each row starts above where the last ended) mean the whole grid is one globally sorted sequence read row by row — a signal to binary search the flattened index.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. Index p in a virtual sorted array of length m*n maps to matrix[p // n][p % n], so you can run an ordinary binary search without physically flattening the grid.

New words, made simpleKnow these before the algorithm
Flattened index
A single number 0..m*n-1 treating the grid as one long row
Row-major order
Reading cells left to right, top row first
Invariant
A condition kept true on every loop iteration
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Scan every cell

Ignores the sorted structure and is far slower than necessary.

Walk all m*n entries and compare each to the target.

Time O(m*n)Space O(1)
Row locate then binary search that row

Correct and fast, but two searches when one suffices.

Binary search first-column values to pick the candidate row, then binary search inside it.

Time O(log m + log n)Space O(1)
Best choiceSingle binary search on the flattened index

One clean search that exploits the full ordering.

Treat the grid as one sorted array of length m*n and map each midpoint back with divmod by n.

Time O(log(m*n))Space O(1)
The rule we keep true

Invariant

If the target exists, its flattened position always lies within [lo, hi].

Why this is correct

Reasoning

The two constraints make the row-major reading strictly increasing, so it is a genuine sorted array; standard binary-search correctness therefore applies, and divmod by n is an exact bijection between flattened indices and cells.

The algorithm in three movesSay these aloud before coding
1Set lo = 0 and hi = m*n - 1 over the virtual flattened array

lo=0 hi=11 mid=5 -> matrix[1][1]=11 > 3, hi=4

2Convert the midpoint p to row p // n and column p % n

lo=0 hi=4 mid=2 -> matrix[0][2]=5 > 3, hi=1

3Compare that cell with target and move lo or hi accordingly

lo=0 hi=1 mid=0 -> matrix[0][0]=1 < 3, lo=1; mid=1 -> 3 == 3

4Return true on a match, false if the range empties

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
31
52
73
104
115
166
207
1 · Readlo=0, hi=11
2 · AskIs the range non-empty?
3 · Update statemid=5 -> matrix[1][1]=11
4 · Result11 > 3, so hi = 4
Key takeaway

The grid behaves as one sorted list; the search converges on cell [0][1] holding 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Guard empty input

    An empty matrix or empty row has nothing to find.

  2. 2
    Lines 5-6Set the virtual bounds

    hi is the last flattened index m*n - 1.

  3. 3
    Lines 9-10Map midpoint to a cell

    divmod by the column count recovers the real row and column.

  4. 4
    Lines 11-16Standard comparison branch

    Move lo up or hi down exactly as in array binary search.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single cell matrix
  • Target smaller than matrix[0][0] or larger than the last cell
  • Target that would fall between two rows and is absent
!

Common beginner mistakes

  • Using m instead of n when doing divmod for the column
  • Off-by-one in hi (must be m*n - 1, not m*n)
  • Forgetting the empty-row guard which makes n undefined
Check your understanding

Why can you map flattened index p to matrix[p // n][p % n] rather than [p // m][p % m]?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search