You are given an m x n integer matrix matrix with two special properties:
Read those two properties together: the rows chain into one another, so the whole grid behaves like a single sorted list that just happens to be printed across several lines.
Given an integer target, return true if target appears anywhere in matrix, and false otherwise.
Your solution must run in O(log(m * n)) time.
i / n → row, i % n → column gives O(1) access to any virtual position, so the matrix already behaves like a flat sorted array.<= target), then binary search inside it: O(log m + log n), which equals O(log(m·n)).n, the number of columns — a flat index advances one column at a time, so every n steps completes one row. Using m happens to work on square matrices, which is exactly why the bug slips through casual testing.(mid / n, mid % n) at the moment of the match, and a sentinel like (-1, -1) when the search range empties. The algorithm is unchanged.i / n and i % n is exactly how computers lay out 2-D arrays in memory — row-major order. The virtual-flattening trick is just binary searching the matrix the way the hardware already sees it.Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true `3` sits in the first row, so the answer is `true`.
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false `13` falls between `11` and `16` but is not present, so the answer is `false`.
- m == matrix.length - n == matrix[i].length - 1 <= m, n <= 100 - -10^4 <= matrix[i][j], target <= 10^4
A sorted matrix that secretly wants to be a sorted array — this problem teaches the single most reusable indexing trick in grid problems: treating a 2-D grid as a 1-D sequence. Master the mapping once and a whole family of matrix problems collapses into plain binary search.
lo..hi with three cases — found, go left, go right.i into a grid cell with row = i / n and col = i % n — division picks the row, remainder picks the column.log(m·n) = log m + log n, so one search over the whole grid costs the same as a row search plus a column search.In plain English: the values, read left-to-right then top-to-bottom, form one non-decreasing sequence of m·n numbers. Formally: given such a matrix and an integer target, report whether target occurs in it, in O(log(m·n)) time.
Worked example — matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
grid: 1 3 5 7
10 11 16 20
23 30 34 60
unrolled: 1 3 5 7 10 11 16 20 23 30 34 60
index: 0 1 2 3 4 5 6 7 8 9 10 11
target 3 → found at flat index 1 → true
Asking two or three sharp questions before touching the keyboard shows an interviewer you design against guarantees, not assumptions.
“Are both sorting properties guaranteed — rows sorted AND each row starting above the previous row?”
Everything hinges on this. If rows and columns are merely sorted independently, the flattened array is no longer sorted and a single binary search silently breaks — that is a different, harder problem.
“Can values repeat inside a row?”
Rows are non-decreasing, so yes within a row — but the strict jump between rows means duplicates never span rows. Either way, membership search is unaffected.
“Can the matrix be a single cell, a single row, or a single column?”
Yes — m and n are each at least 1. The flat-index search handles all three shapes with no special-casing, which is part of its beauty.
“What if target is smaller than the first value or larger than the last?”
The search range empties after a few halvings and we return false — no sentinel checks needed.
“How large can the matrix get, and is the required complexity firm?”
Up to 100 × 100 = 10^4 cells — a linear scan would actually pass, but the statement demands O(log(m·n)), so the constraint is about technique, not survival.
Before I code, I want to confirm the two structural guarantees: every row is sorted, and each row starts strictly after the previous row ends.
Those two together mean the matrix read in row-major order is one fully sorted array of m times n values.
So my plan is a single binary search over flat indices 0 to m·n − 1, converting each mid back to a cell with division and modulo — that gives the required logarithmic time.
Row-sortedness orders values within a line; the strict jump between rows orders the lines against each other. Chain them and the row-major reading of the grid is globally non-decreasing:
[ 1 3 5 7 ][ 10 11 16 20 ][ 23 30 34 60 ] row 0 ends ≤ 10 = row 1 starts ≤ … — one sorted sequence
Copying the grid into a real 1-D array costs O(m·n) time and space — and it is pointless. Flat position i lives at row i / n, column i % n (integer division). That is O(1) arithmetic, so the matrix already is random-access sorted storage.
With a sorted virtual array of length m·n and O(1) access, the textbook loop applies unchanged: probe the middle, compare, discard half. That is O(log(m·n)) — exactly what the statement demands, with not one line of new algorithmic machinery.
| Brute force | Staircase | Binary search | |
|---|---|---|---|
| Time | O(m·n) | O(m + n) | O(log(m·n)) |
| Space | O(1) | O(1) | O(1) |
Full, runnable code for every approach lives in the Approaches selector below.
Key takeaway
When a 2-D structure has a global sorted order and O(1) cell access, binary search it through a virtual flat index — row = i / n, col = i % n. Unroll the grid in your head, never in memory.
lo = 0, hi = m·n − 1
while lo ≤ hi:
mid = (lo + hi) / 2
val = matrix[mid / n][mid % n]
if val == target: return true
if val < target: lo = mid + 1
else: hi = mid − 1
return false