The problem
You get a grid of numbers where each row is sorted left to right, and the first number of each row is bigger than the last number of the row before. Decide whether a target number is in the grid.
Input: [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 16 Output: true
Picture it
Picture an apartment block: each floor is a row and apartment numbers keep increasing along a floor and then onto the next floor up. Read in order, the whole building is one long sorted list. So we binary search positions 0…(rows×cols − 1), and an elevator converts a position into (floor = position ÷ cols, door = position mod cols).
How to recognise it
- The grid is sorted in reading order: each row is sorted, and each row starts after the previous row ends. Read row by row, it is one long sorted list.
- You only need to know whether the target is there, and the problem asks for O(log(m · n)) time.
- Any structure that can be numbered in sorted order can be binary searched, as long as you can turn a number back into a position. Here
divmoddoes that. - Up to 100 × 100 cells.
Start with brute force
Check every row for the target.
def search_matrix_brute(m, target):
return any(target in row for row in m)
Time is O(m · n) and space is O(1). With LeetCode's 100 × 100 limit that is at most 10^4 comparisons, which would pass, but the problem asks for O(log(m · n)): about 14 comparisons for the same grid. The brute force also ignores both kinds of order in the grid.
From brute force to the idea
- Find the waste. The grid is fully sorted, yet the brute force looks at every cell.
- Flatten it in your head. Number the cells 0 to
rows * cols - 1in reading order. Because each row starts above the end of the row before, these numbers list the values in sorted order. - Turn a number back into a cell. Cell number
midis in rowmid // colsand columnmid % cols.divmod(mid, cols)gives both at once. Dividing by the number of columns is essential: each row holdscolscells. - Run ordinary binary search. Keep
lo..hiinclusive. Comparem[r][c]with the target and moveloorhipastmid, exactly as in a one-dimensional search. - No list is built. The flattening is only arithmetic, so no copy of the grid is made.
This is the key idea: a grid sorted in reading order is one sorted list, and divmod(mid, cols) finds any position in it.
A two-step search also works: binary search the first column to find the row, then binary search that row. It has the same O(log m + log n) cost.
The key idea
Treat the 2-D grid as one sorted 1-D list and binary search it: O(log(rows × cols)).
Python solution
def search_matrix(m, target):
rows, cols = len(m), len(m[0])
lo, hi = 0, rows * cols - 1 # treat it as one long sorted list
while lo <= hi:
mid = (lo + hi) // 2
r, c = divmod(mid, cols) # which floor, which door
if m[r][c] == target:
return True
if m[r][c] < target:
lo = mid + 1
else:
hi = mid - 1
return FalseIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(m · n): every cell may be checked | O(1) |
| Flattened binary search (shown code) | O(log(m · n)): the range of cell numbers halves each step | O(1): a few integers |
Edge cases
- The example (target 16): returns
True; target 13 returnsFalse. - A 1 × 1 grid (
[[5]]):lo == hi == 0, returnsTruefor 5. - One row or one column (
[[1, 3, 5]]or[[1], [3], [5]]): the arithmetic still works, sincecolsis 3 or 1. - Target outside the range (0 or 61 in the example): the range empties off one end and the function returns
False. - Empty grid:
len(m[0])raisesIndexErroron[]. LeetCode promises at least one row and column, so the shown code does not check.
Common mistakes
- Using
divmod(mid, rows). It only works by luck on square grids; on others it reads the wrong cell or goes out of range. - Setting
hi = rows * colsand keepingwhile lo <= hi. When the target is larger than every value,midreachesrows * colsand the code reads past the last row. - Using the staircase walk from the next exercise. It is correct here too, but O(m + n), not the O(log(m · n)) the problem asks for.
- Binary searching only the rows by their first value and forgetting that the target may lie in the row before the first larger start.
Now each row is sorted left to right and each column top to bottom, but a row may start below the end of the previous row (LeetCode 240). Flattening no longer gives a sorted list. Decide whether the target is present. Describe your approach, then write it if you like.
Compare with our answer
Start at the top-right corner. Everything below it in its column is bigger, and everything left of it in its row is smaller. So if the value is too big, the whole column is useless: move left. If it is too small, the whole row is useless: move down.
def staircase(m, target):
r, c = 0, len(m[0]) - 1 # top-right corner
while r < len(m) and c >= 0:
if m[r][c] == target:
return True
if m[r][c] > target:
c -= 1 # whole column below is bigger too
else:
r += 1 # whole row to the left is smaller too
return False
Each step removes a row or a column, so time is O(m + n). Space is O(1).
A strong answer mentions: why the top-right (or bottom-left) corner works and the top-left does not, that each step discards a full row or column, and the O(m + n) bound.
1. A grid stores 3,000 ticket numbers, 50 per row, sorted in reading order like this problem. Which approach finds whether a ticket number is present fastest?
The whole grid is sorted in reading order, so one binary search over the flattened numbering takes about 12 steps. The staircase walk is O(m + n), and searching each row in turn is O(m log n).
2. Why must the shown code use divmod(mid, cols) and not divmod(mid, rows)?
In reading order, every full row before cell mid contributes cols cells, so mid // cols is the row and mid % cols the column. Python lists of lists are stored row by row; dividing by rows reads the wrong cells on non-square grids.
3. A learner sets hi = rows * cols and keeps the rest of the shown code. With the example grid, which target now breaks it?
For 61, lo keeps moving right until mid is 12, which is row 3: there are only rows 0 to 2, so m[3] raises IndexError. Smaller targets stop before mid reaches the extra position.
Score 60% or more and the lesson is marked complete.