LC 74 · Medium · Template A · index remap

Search a 2D Matrix

A grid whose rows are sorted and where each row starts above where the previous row ended.

Recognise it

Before any code, what in the question tells you this is the pattern?

A matrix where each row is sorted AND the first value of each row exceeds the last of the previous row. That second condition is the tell: the whole grid is one sorted array wearing a 2D costume.

The brute force

Always have this one ready. It is the honest starting point, and it is what the real solution improves on.

Scan every cell of the matrix and compare it to the target.

O(m * n) time and O(1) space.

A slightly better attempt is to binary search the rows to find the right one, then binary search inside it, giving O(log m + log n). That is already fine. But noticing that log m + log n equals log(m * n) tells you those two searches were always one search wearing a disguise, and writing it as one is shorter and has fewer places to make an off-by-one mistake.

The approach

The idea in plain language, before it becomes syntax.

Read the guarantee carefully. Every row is sorted, and the first value of a row is greater than the last value of the row above it. Put those two facts together and the matrix, read left to right and then top to bottom, is one long sorted list. The rows are just line breaks.

So pretend the line breaks are not there. Binary search the index range from 0 to rows * cols - 1 exactly as you would on a flat array. The only extra work is that you cannot index a matrix with a single number, so at the moment you need to read a value you convert: the row is the index divided by the column count, and the column is the remainder.

This is worth recognising as a technique in its own right. The array you search does not have to exist in memory. Here it is a view over a matrix, and in other problems it is a range of possible answers. What binary search actually needs is an ordered index space and a way to ask a question at a given index.

A row-sorted matrix flattened into one sorted list by index remapping.The matrix is already one sorted list, folded into rows.13571011162023303460unfold13571011162023303460index i -> row = i / cols, col = i % colsRun one ordinary binary search over 0 .. rows*cols-1 and translate only when you read.
Search a 2D Matrix: the idea in one picture.edit source
Turning a flat index into a row and column.index 6, cols = 4row = 6 / 4 = 1col = 6 % 4 = 2Divide by the column count, not the row count. Square matrices hide the mistake.
Do the conversion at the single point where you read a value.

The algorithm

The same idea again, as steps you could follow with a pencil.

Flowchart for searching a matrix by treating it as a flat sorted array.lo = 0, hi = rows * cols - 1mid = (lo + hi) / 2value = m[mid / cols][mid % cols]compare, then halveOne search, not two.
Search a 2D Matrix: the loop, step by step.edit source
Time O(log(m·n))Space O(1)

The solution

Now the code, and why each decision in it is the way it is.

search_a_d_matrix
def searchMatrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // n][mid % n]   # flatten -> 2D
        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

The division and modulo happen inside the loop, at the single point where a value is read. Converting anywhere else spreads the mapping across the function and gives you more chances to swap the operands.

Note that cols, not rows, is the divisor in both expressions. Using the wrong dimension still produces valid indices on a square matrix, so it will pass your mental test and fail on anything rectangular. Test with a matrix that is not square.

Everything else is the plain template from LC 704. That is the payoff of the remap: no new loop shape to get right.

Where people slip

  • Only valid when rows chain together (row i+1 starts above row i ends). If not, this is a different problem. See the follow-up.
  • Index mapping: row = mid // n, col = mid % n. Mixing up n (cols) and m (rows) is the classic bug.

Your notes

What tripped you up here? Write it in your own words.

Where interviewers go next

Solve this one and the follow-up is usually a variation rather than a new idea. Knowing the connection is worth more than memorising each problem.

  • Search a 2D Matrix IILC 240Rows and columns sorted, but NOT globally flattenable. Start at top-right corner and walk: go left if too big, down if too small. O(m+n), the expected answer, not binary search.
  • Row-then-column searchvariantBinary search to find the candidate row, then binary search within it. O(log m + log n). Equivalent, sometimes cleaner to explain.