LeetCode 74 ·
Medium
Search a 2D Matrix
Search a target in a matrix whose rows are sorted and each row starts after the previous ends.
Try it
Step through the core mechanic. The simulator below runs the binary search shape this problem is built on.
Interactive · Binary search walkthrough Sorted array; halve the search range at each step.
0
-7
L
1
-3
2
0
3
2
4
5
5
8
6
11
7
14
8
17
9
21
10
25
11
30
H
start: lo=0, hi=11, mid=5, a[mid]=8
range12 log₂(n)≤ 4 step0 / 3
Why binary search is O(log n).
Each step halves the search range. Starting from
n, after
k steps the range is n / 2ᵏ; the search ends when
this drops below 1, so k ≤ log₂(n). For n = 10⁹,
that's ≤ 30 steps. The interview corollary: if the constraint is
n ≤ 10⁹, you need an O(log n) approach — binary search is
usually the one.The approach
Flatten conceptually: index m maps to (m / cols, m % cols). One binary search over [0, rows·cols) does it in O(log mn).
| Aspect | Value |
|---|---|
| Pattern | Binary search |
| Recognise it by | Row-sorted, column-sorted matrix — treat as one sorted array. |
| Time complexity | O(log mn) |
| Space complexity | O(1) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.