What two different orderings can "sorted matrix" mean, and why does search differ?
answer
- two grids, two different promises
- does the next row start higher?
- one long sorted sequence, or not
- flattening needs a global order
- corner walk versus flat binary search
basics
~20 s"Sorted matrix" means one of two things: fully sorted row-major, where the grid reads as one non-decreasing sequence and binary search costs O(log mn); or merely row- and column-sorted, which has no global order and needs corner elimination at O(m+n).
solid answer
~50 sTwo grids can both be described as sorted and still need completely different algorithms. In a **fully sorted** grid — a warehouse shelf catalog where the first code on each shelf is at least the last code on the shelf above — reading row by row yields one non-decreasing sequence of length `m*n`, so you binary search the flat index range and translate each midpoint back to a cell: O(log mn). In a grid that is only **row- and column-sorted** — a price grid climbing left to right and top to bottom — no such global order exists: a row can end at 90 while the next row starts at 5. Flattening it and binary searching still terminates in O(log mn) and still returns an answer; the answer is just wrong, reporting "not found" for values that are present. That shape needs a corner walk at O(m+n).
go deeper
Recall that "sorted matrix" is ambiguous and name both shapes: fully sorted row-major versus only rows-and-columns sorted. Be ready to say which search each one allows and roughly what it costs.
Explain why flattening is legal only under the stronger guarantee — binary search discards a half based on a total order that the weaker shape does not provide — and describe the silent wrong answer it produces.
Show the habit of checking the guarantee before choosing the algorithm, and of preferring the slower correct method when a caller's data cannot be verified. Be able to say why square test fixtures hide this bug.
Own the framing that the two shapes are different data contracts, not two tricks. Argue when it is worth paying to maintain the stronger ordering versus accepting the weaker one and its O(m+n) reads.
## Two guarantees that share one word An interviewer says "you are given a sorted matrix" and then waits to see whether you ask *which kind*. There are two distinct guarantees hiding behind that phrase, and they are not the same problem. ### Guarantee A — fully sorted (row-major continuation) Every row is non-decreasing left to right, **and** the first entry of each row is at least the last entry of the row above. Picture a warehouse shelf catalog printed as m shelves down and n slots across: shelf 0 holds codes 100, 104, 109, 115 and shelf 1 starts at 121. Reading the grid row by row produces one non-decreasing sequence of length `m*n`. That is exactly what binary search needs: a total order over positions, random access to any position, and a monotone predicate ("is the entry at flat position i less than the target?"). You binary search the flat index range `0 .. m*n-1`, translating each midpoint back into a cell before comparing. Cost: O(log mn) probes, which is the same thing as O(log m + log n). ### Guarantee B — row- and column-sorted (a Young-tableau shape) Every row increases left to right and every column increases top to bottom, and that is **all**. A price grid whose rows are package sizes and whose columns are contract tiers has exactly this shape: price climbs along both axes because both axes are ordered by something that raises price. Nothing ties the end of one row to the start of the next. Row 0 may end at 90 while row 1 starts at 5, because row 1's cheapest tier is still cheaper than row 0's most expensive tier. ### Why flattening breaks on B, and breaks silently Binary search's correctness rests on one invariant: if the target exists, it lies inside the current `[lo, hi]` window. Discarding half the window is only legal because the probed value is comparable to *everything* on the discarded side. Under guarantee B, reading row-major does not produce a sorted sequence, so "every entry before flat position i is at most the entry at i" is false. The search still terminates. It still runs in O(log mn). It still returns an answer — the wrong one. It reports "not found" for values physically sitting in the grid. No crash, no out-of-range index, no exception: a pure correctness bug, and one that fixtures built from small, tightly packed square grids frequently fail to expose, because on a tightly packed grid the two guarantees happen to coincide. This is the single most common failure in this family, which is why the first sentence out of your mouth should name which guarantee you have. ### What guarantee B does support B still orders each row and each column, so you can eliminate an entire line per comparison by entering at a corner where the comparison is decisive. The top-right entry is the maximum of its row and the minimum of its column: too large rules out the whole column, too small rules out the whole row. Each step drops one row or one column, so the walk visits at most m + n − 1 cells — O(m+n). ### The containment almost nobody states Guarantee A **implies** guarantee B. If the grid reads row-major as one non-decreasing sequence, then rows increase and columns increase as well. So the corner walk is *correct* on a fully sorted grid — merely slower, O(m+n) rather than O(log mn). The converse does not hold. Saying this out loud signals that you are reasoning about the guarantees as constraints that nest, rather than memorising two recipes. ### Telling them apart in thirty seconds Check whether the last entry of each row is at most the first entry of the next; one pass down that boundary answers it in O(m) probes. If the statement only promises that the two axes are sorted, assume B. And if a caller hands you a grid at run time and you cannot verify the stronger guarantee, use the algorithm the *weaker* guarantee supports: being asymptotically slower is recoverable, being wrong is not. ### Cost at realistic sizes | Grid shape | Fully sorted (flat binary search) | Row/column sorted (corner walk) | Scan every cell | |---|---|---|---| | 1,000 x 1,000 | ~20 probes | ~2,000 probes | 1,000,000 | | 10 x 100,000 | ~20 probes | ~100,010 probes | 1,000,000 | Both ordered methods crush the full scan. The gap *between* them matters when probes are expensive or the search sits on a hot path — but the gap in correctness is absolute, and that is the one the question is really testing.
- If you flatten a merely row- and column-sorted grid and binary search it, what actually happens?It runs to completion in O(log mn) and usually returns "not found" for a value that is present. The discard step assumes everything before the probed flat position is smaller, which is false the moment a row starts below where the previous row ended. There is no crash to catch, so the bug ships.
- Does a fully sorted grid also satisfy the row- and column-sorted property?Yes — the stronger guarantee implies the weaker one, so a corner walk is correct on a fully sorted grid, just slower at O(m+n) instead of O(log mn). The reverse fails: row- and column-sorted says nothing about how one row relates to the next.
- At the whiteboard, how would you verify which guarantee a grid gives you?Compare the last entry of each row with the first entry of the next, top to bottom — m − 1 comparisons. If every pair is ordered, the grid is fully sorted and flattening is safe. If any pair inverts, only the per-row and per-column guarantee holds and you must use corner elimination.
One grid is a book: each page continues the previous page's story in order. The other is a train timetable where every row and every column climbs on its own, but the rows do not chain end to end.
saying these in an interview costs you the question
- Says any sorted matrix supports O(log mn) binary search
- Assumes row- and column-sorted implies one global order
- Never asks which of the two guarantees holds
- Thinks the corner walk is wrong on a fully sorted grid
- Treats a wrong "not found" as a missing edge case, not a broken invariant