Search a 2D Matrix
Find a number in a grid whose rows are sorted and follow on from each other, using one binary search.
- 2D matrix as a 1D sorted array
- Classic binary search
Before this, know: Binary search (lo, hi, mid), 2D arrays (rows and columns), Integer division and remainder (// and %)
A matrix is a grid of numbers: a list of rows, each row a list of the
same length. matrix[r][c] is the number in row r, column c (both counted
from 0). We say the matrix is m × n: m rows and n columns.
This matrix has two special properties:
- Each row is sorted from left to right.
- The first number of each row is bigger than the last number of the row above it.
Return true if target is somewhere in the matrix, false otherwise.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 3 | 5 | 7 |
| 1 | 10 | 11 | 16 | 20 |
| 2 | 23 | 30 | 34 | 60 |
With target = 3 the answer is true (row 0, column 1). With target = 13 it’s
false. Rows and columns have between 1 and 100 items, and the problem asks for
O(log(m × n)) time: a binary search, not a scan.
Thanks to property 2, the whole grid is really one long sorted list that has been folded into rows. We don’t need to search rows and then columns. We can binary search the long list directly, as long as we can turn a position in that list into a row and a column. That’s exactly the cinema trick:
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 4 | 5 | 6 | 7 |
| 2 | 8 | 9 | 10 | 11 |
- 10
- 31
- 52
- 73
- 104
- 115
- 166
- 207
- 238
- 309
- 3410
- 6011
// means “divide and round down” (in JavaScript: Math.floor(a / b)), and %
means “the remainder after dividing” (the same in both languages).
Pause and think
row = 6 // 4 = 1, col = 6 % 4 = 2. matrix[1][2] is 16, which is
indeed the 7th number (position 6) of the long list
1, 3, 5, 7, 10, 11, 16, ….
Look at every cell, row by row, until you find the target.
Brute force: check every cell
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 3 | 5 | 7 |
| 1 | 10 | 11 | 16 | 20 |
| 2 | 23 | 30 | 34 | 60 |
- target
- 13
- cells checked
- 1
- result
- —
- Checking
- Already checked
- Target
Look #1: matrix[0][0] = 1, not 13.
Which line is running?
function searchMatrix(matrix, target) { for (const row of matrix) { for (const value of row) {Running now: if (value === target) return true; } } return false;}Brute force: check every cell
function searchMatrix(matrix, target) { for (const row of matrix) { for (const value of row) { if (value === target) return true; } } return false;}def search_matrix(matrix, target): for row in matrix: for value in row: if value == target: return True return FalseIt checks up to every cell: m × n looks. For the 3 × 4 example, 12 looks. For a
100 × 100 matrix, 10,000 looks. That’s O(m × n),
and it throws away all the sorting. Binary search over 10,000 items needs about 14 looks.
When a grid, read row by row, is fully sorted, you can pretend it’s a plain
array of length m × n and run the classic binary search on it. You never build
that array; you convert each position on the fly.
Pattern
2D matrix as a 1D sorted array
Use it when: a grid is sorted in reading order (each row sorted, each row starts after the previous row ends).
Signal words
- “m x n matrix”
- “each row is sorted”
- “each row starts after the previous row ends”
- “O(log(m * n))”
- Let
mbe the number of rows andnthe number of columns. - Set
lo = 0andhi = m × n − 1: every position is possible. - While
lo <= hi: computemid = lo + (hi − lo) // 2. - Convert
midto a cell:row = mid // n,col = mid % n. Readvalue = matrix[row][col]. - If
valueequals the target, returntrue. If it’s smaller,lo = mid + 1. If bigger,hi = mid − 1. - If the loop ends, return
false.
Press Play. The grid on top and the long list underneath are the same
numbers, coloured the same way. Watch mid jump in the list, then watch the
row and column light up in the grid as mid is converted. Try the one-row and
1 × 1 edge cases too.
One binary search over the flattened matrix
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 3 | 5 | 7 |
| 1 | 10 | 11 | 16 | 20 |
| 2 | 23 | 30 | 34 | 60 |
- n (columns)
- 4
- mid
- —
- row
- —
- col
- —
- value
- —
- target
- 3
- result
- —
- 10
- 31
- 52
- 73
- 104
- 115
- 166
- 207
- 238
- 309
- 3410
- 6011
- Still possible (lo..hi)
- mid
- Thrown away
- Target
- Not the target
3 rows × 4 columns = 12 numbers. Read row by row, they form one sorted list with positions 0 to 11. We binary search that list: lo = 0, hi = 11.
Which line is running?
function searchMatrix(matrix, target) { const m = matrix.length; // number of rows const n = matrix[0].length; // number of columns let lo = 0;Running now: let hi = m * n - 1; // pretend the matrix is one long sorted list while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); const row = Math.floor(mid / n); // how many full rows come before mid const col = mid % n; // how far along that row mid is const value = matrix[row][col]; if (value === target) { return true; } else if (value < target) { lo = mid + 1; } else { hi = mid - 1; } } return false;}Binary search on the flattened matrix
function searchMatrix(matrix, target) { const m = matrix.length; // number of rows const n = matrix[0].length; // number of columns let lo = 0; let hi = m * n - 1; // pretend the matrix is one long sorted list while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); const row = Math.floor(mid / n); // how many full rows come before mid const col = mid % n; // how far along that row mid is const value = matrix[row][col]; if (value === target) { return true; } else if (value < target) { lo = mid + 1; } else { hi = mid - 1; } } return false;}def search_matrix(matrix, target): m = len(matrix) # number of rows n = len(matrix[0]) # number of columns lo, hi = 0, m * n - 1 # pretend the matrix is one long sorted list while lo <= hi: mid = lo + (hi - lo) // 2 row = mid // n # how many full rows come before mid col = mid % n # how far along that row mid is value = matrix[row][col] if value == target: return True elif value < target: lo = mid + 1 else: hi = mid - 1 return FalseJavaScript sets lo and hi on two lines and has closing braces, so its line
numbers run ahead of Python’s; we give both.
- Line 1: define the function. (LeetCode:
var searchMatrix = function(matrix, target), or a method ofclass Solutionin Python.) - Lines 2–3:
m= how many rows,n= how many items per row. The problem promises at least one row and one column, somatrix[0]is safe. - Lines 4–5 (JS) / line 4 (Py): positions run from 0 to
m × n − 1, the last cell. That’s the long list we pretend exists. - Line 7 (JS) / line 6 (Py): the classic middle.
- Line 8 (JS) / line 7 (Py):
row = mid // n. Every full row beforemidholdsnitems, so dividing byn(rounded down) counts the full rows. - Line 9 (JS) / line 8 (Py):
col = mid % n, what’s left over after those full rows: how far along its own rowmidis. - Line 10 (JS) / line 9 (Py): read the real cell.
- Lines 11–17 (JS) / 10–15 (Py): exactly the classic binary search: found, go right, or go left.
- Line 19 (JS) / 16 (Py): the range is empty, so the target isn’t in the matrix.
The 3 × 4 example (n = 4) with target = 3:
| lo | hi | mid | row = mid // 4 | col = mid % 4 | value | next |
|---|---|---|---|---|---|---|
| 0 | 11 | 5 | 1 | 1 | 11 | 11 > 3: hi = 4 |
| 0 | 4 | 2 | 0 | 2 | 5 | 5 > 3: hi = 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 < 3: lo = 1 |
| 1 | 1 | 1 | 0 | 1 | 3 | 3 = 3: return true |
The first line of the table (mid = 5) is the mapping at work: position 5 is 5 // 4 = 1 full row in, and
5 % 4 = 1 step along it, so it’s matrix[1][1] = 11.
Check every cell
Time
O(m × n)
Up to one look per cell: 10,000 looks for a 100 × 100 matrix.
Space
O(1)
Just the loop variables.
Binary search on the flattened matrix
Time
O(log(m × n))
Each round halves the positions left. 10,000 cells take about 14 rounds.
Space
O(1)
lo, hi, mid, row and col. We never build the long list.
What to say out loud, in this order:
- “Rows are sorted, and each row starts after the previous one ends, so reading row by row gives one sorted list.”
- “I can binary search that list without building it: position
kismatrix[k // n][k % n].” - Mention the alternative: “binary search to pick the row, then binary search inside the row. Same O(log(m × n)), but two loops.”
- Cost: O(log(m × n)) time, O(1) space.
- Dry-run the mapping for one
midso the interviewer sees it’s right.
Likely follow-up questions:
- “What if each row and each column is sorted, but rows don’t follow on?” That’s Search a 2D Matrix II: start at the top-right corner and step left or down (O(m + n)). The flattening trick no longer works, because the long list isn’t sorted.
- “Return the position instead of true/false?” Return
[row, col].
Related problems:
- Binary Search (this week): the template this builds on.
- Find Minimum in Rotated Sorted Array (this week): binary search when the sorted order has a twist.
- The week 3 overview has the template.