Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Because each row is sorted and the first element of each row exceeds the last of the previous row, the whole matrix is one big sorted array read row by row. Binary search over the virtual index range [0, m*n − 1], mapping index `idx` to `matrix[idx / n][idx % n]`. O(log(m*n)) time, O(1) space — no need for a two-step row-then-column search.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you spot that the matrix is a flattened sorted array and can do the index ↔ (row, col) arithmetic correctly, rather than writing a clumsy nested search.
Where candidates slip
Dividing/modding by the wrong dimension (m vs n), or doing a linear row scan then binary search within a row (O(m + log n) instead of O(log(m*n))).
How to stand out
State the key property out loud, write the single binary search over m*n, and contrast it with the top-right staircase needed for the LeetCode 240 variant where rows don't chain.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewSearch a sorted matrixDoes each row start above the previous row's end?YesNo (only row+col sorted)Explore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Two-Step: Find Row, Then Search It (Baseline)
1Hint 1Explore hintHide hint
Each row covers a contiguous value range. How would you first pick the row whose range could contain the target?
2Hint 2Explore hintHide hint
Scan rows to find the one where matrix[row][0] <= target <= matrix[row][n-1], then binary search inside it.
3Hint 3Explore hintHide hint
The row scan is O(m); the inner search is O(log n). Correct, but we can fold both into one binary search.
A · Core idea
Walk the rows to find the one whose first and last values bracket the target, then binary search within that row.
Why mention it. It demonstrates you understand that each row is a value band, and it's an easy stepping stone. Why we improve it. The row scan is linear in m, so the total is O(m + log n) — short of the O(log(m*n)) target. Replacing the linear row search with binary search (or flattening) removes the O(m) term.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 16row 0
range [1,7], 16 > 7 → skip
next rowtrueC · Code with teaching comments
Reference implementation previewpublic boolean searchMatrix(int[][] matrix, int target) { int n = matrix[0].length; for (int[] row : matrix) { if (target >= row[0] && target <= row[n - 1]) { int lo = 0, hi = n - 1;Explore the full codeHide the full code
D · Why it works and complexityO(m + log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Both the choice of row and the position within the row are binary-searchable, so doing one of them linearly leaves performance on the table. The cleanest fix is to stop thinking in rows at all.
ComplexityO(m + log n) time, O(1) space — Linear scan over m rows to locate the candidate row, plus a log n binary search inside it.
E · Edge cases and pitfalls2Linear row scan keeps an O(m) term — fine for correctness, short of the required bound.Explore edge casesHide edge cases
Pitfalls
- Linear row scan keeps an O(m) term — fine for correctness, short of the required bound.
- Forgetting that exactly one row can bracket the target, and continuing to scan after finding it.
Approach 2 of 2 · Optimal
Flatten to a Virtual 1D Array (Optimal)
1Hint 1Explore hintHide hint
Both properties together mean reading the grid row by row gives a fully sorted sequence. What if you pretended it was a 1D array of length m*n?
2Hint 2Explore hintHide hint
Binary search indices 0..m*n-1. To read 'element idx', convert it to a cell: row = idx / n, col = idx % n.
3Hint 3Explore hintHide hint
Everything else is the standard inclusive-bounds binary search — compare, then move lo or hi past mid.
A · Core idea
Treat the matrix as a sorted array of length m*n indexed 0 .. m*n - 1, and binary search it.
Why this is valid. Property one (rows sorted) plus property two (each row starts above the previous row's end) means concatenating the rows top-to-bottom yields a globally non-decreasing array. So the abstract 1D view is sorted, and binary search applies directly.
The index mapping. A virtual index idx corresponds to cell (idx / n, idx % n) where n is the number of columns. Integer division idx / n counts how many full rows precede idx (the row), and idx % n is the offset within that row (the column). This is exactly how row-major memory layout works. The single most common bug is dividing/modding by the row count m instead of the column count n; always use n, the width.
The search itself. Standard inclusive-bounds binary search: lo = 0, hi = m*n - 1, mid = lo + (hi - lo) / 2, read val = matrix[mid / n][mid % n]. If val == target return true; if val < target move lo = mid + 1; else hi = mid - 1. Falling out of the loop means absence → false.
Why it beats the two-step approach. There is no separate O(m) row-selection pass — choosing the row and the column happens implicitly inside the one binary search, giving O(log(m*n)) = O(log m + log n).
Boundary safety. n >= 1 by the constraints, so dividing by n is safe and matrix[0] exists. The inclusive <= loop correctly handles the single-cell matrix (m == n == 1).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 16Array state
lo=0, hi=11
mid=5 → 11 < 16 → discard left half
trueC · Code with teaching comments
D · Why it works and complexityO(log(m*n)) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Recognising hidden 1-D structure inside a 2-D (or n-D) layout is a recurring superpower: the same idx / width, idx % width mapping linearises image buffers, flattened DP tables, and serialized grids. When a problem hands you a 'global ordering' guarantee across a structured container, ask whether you can binary search the flattened view.
ComplexityO(log(m*n)) time, O(1) space — One binary search over m*n virtual elements → log₂(m*n) iterations, each O(1) (a divide, a mod, one comparison). O(1) extra space.
E · Edge cases and pitfalls8matrix = [[1]], target = 1 — lo=hi=0, mid=0 → matrix[0][0]=1 == target → true.Explore edge casesHide edge cases
Edge cases handled
matrix = [[1]], target = 1lo=hi=0, mid=0 → matrix[0][0]=1 == target → true.matrix = [[1]], target = 2mid=0, 1 < 2 → lo=1, loop ends → false.target smaller than matrix[0][0]Every val > target → hi marches to -1 → false, no out-of-bounds.single row [[1,3,5]], target = 5n=3, m=1; behaves as plain 1D binary search → finds 5 at index 2.
Pitfalls
- Using m instead of n for the / and % — maps to the wrong cell and reads garbage.
- Setting hi = m * n (exclusive) but looping with `<=` — off-by-one out of bounds.
- Reverting to an O(m) row scan and missing the O(log(m*n)) requirement.
- Applying this to a matrix where rows don't chain (LeetCode 240) — the flatten property fails.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int lo = 0, hi = m * n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong dimension in index mapping
Row-major flattening uses the column count. Dividing by m (rows) instead of n (columns) maps virtual indices to the wrong cells and silently returns wrong answers.
Explore the code comparisonHide the code comparison
Wrong dimension in index mapping
Row-major flattening uses the column count. Dividing by m (rows) instead of n (columns) maps virtual indices to the wrong cells and silently returns wrong answers.
Don't write this
int val = matrix[mid / m][mid % m]; // m = rows — WRONGWrite this instead
int val = matrix[mid / n][mid % n]; // n = columns2Exclusive hi with inclusive loop
Setting hi = m*n (one past the last index) but looping with lo <= hi lets mid reach m*n-... wait, it lets the search read index m*n which is out of bounds. Match the bound to the loop condition.
Explore the code comparisonHide the code comparison
Exclusive hi with inclusive loop
Setting hi = m*n (one past the last index) but looping with lo <= hi lets mid reach m*n-... wait, it lets the search read index m*n which is out of bounds. Match the bound to the loop condition.
Don't write this
lo, hi = 0, m * n # exclusive end
while lo <= hi: # inclusive loop → can index m*n
mid = lo + (hi - lo) // 2
val = matrix[mid // n][mid % n]Write this instead
lo, hi = 0, m * n - 1 # inclusive end
while lo <= hi:
mid = lo + (hi - lo) // 2
val = matrix[mid // n][mid % n]Revise
Carry the pattern into the interview
Pattern to remember
Flatten to a virtual sorted array + binary search
Code pattern to memorize
m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
val = matrix[mid // n][mid % n]
if val == target: return True
elif val < target: lo = mid + 1
else: hi = mid - 1
return FalseRules to remember
- 1Map a 1D index to 2D with
row = idx / n,col = idx % nwherenis the number of columns. - 2Divide and mod by the column count
n, never the row countm— swapping them is the classic bug. - 3Search range is
[0, m*n − 1]inclusive, with the samewhile (lo <= hi)template as 1D binary search. - 4This works only because rows are sorted and each row's first value > previous row's last value — confirm that property before flattening.
- 5If only rows (not the row-to-row join) are sorted, use the staircase O(m+n) search from the top-right instead (that's LeetCode 240).
Use this pattern when
- A fully 'row-major sorted' matrix where the flatten-to-1D property holds
- You need O(log(m*n)) membership in a sorted grid
- Any 2D structure that is secretly a 1D sorted sequence
Choose another pattern when
- Matrix is only sorted within rows AND within columns but rows don't chain (LeetCode 240) → top-right staircase, O(m+n)
- Matrix is unsorted → no binary search; hashing or full scan
- You need the position (row, col), not just presence → still fine, just convert mid back
Interview takeaway
The reusable trick is recognising that a constraint ('first of each row > last of the previous') turns a 2D problem into a 1D one. Index mapping via `/n` and `%n` is the bridge; once you see it, matrix search collapses to ordinary binary search.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternBinary search on a flattened sorted container. Recognise it when a 2D (or n-D) structure carries a global ordering guarantee so it can be viewed as one sorted 1D array. The index ↔ coordinate mapping (idx/n, idx%n) is the reusable bridge.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Search a 2D Matrix IIComing soonRows and columns sorted but rows don't chain — walk from the top-right corner, O(m+n).
- Binary SearchThe 1D core this reduces to once you flatten the grid.
- Kth Smallest Element in a Sorted MatrixComing soonBinary search on the value range, counting elements ≤ mid per row.
- Search in Rotated Sorted ArrayAnother 'adapt binary search to a transformed layout' problem.