Skip to content
16-Week DSA Roadmap
LeetCode #74MediumProblem 7 of 8

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 %)

The problem in plain English

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:

  1. Each row is sorted from left to right.
  2. 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.

0123
0
1
3
5
7
1
10
11
16
20
2
23
30
34
60
A 3 × 4 matrix. Reading it like a book (left to right, then the next row) gives 1, 3, 5, 7, 10, 11, … 60: one sorted list.

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.

Before you code: think it through

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:

0123
0
0
1
2
3
1
4
5
6
7
2
8
9
10
11
Each cell's number here is its position in the long list. Position k lives at row = k // 4 and col = k % 4, because each row holds n = 4 items.
  1. 10
  2. 31
  3. 52
  4. 73
  5. 104
  6. 115
  7. 166
  8. 207
  9. 238
  10. 309
  11. 3410
  12. 6011
The same 12 numbers as one sorted list. Position 9 (shaded) is matrix[2][1] = 30.

// 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

The matrix has n = 4 columns. Which row and column is position 6? What number is there in the matrix above?

Approach 1: Brute force

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

0123
0
1
3
5
7
1
10
11
16
20
2
23
30
34
60
variables
target
13
cells checked
1
result
—
  • Checking
  • Already checked
  • Target

Look #1: matrix[0][0] = 1, not 13.

Step 1 / 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 False

Why is it slow?

It 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.

The pattern: treat the 2D matrix as a 1D sorted array

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

Template

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))”

Approach 2: One binary search over the flattened matrix

  1. Let m be the number of rows and n the number of columns.
  2. Set lo = 0 and hi = m × n − 1: every position is possible.
  3. While lo <= hi: compute mid = lo + (hi − lo) // 2.
  4. Convert mid to a cell: row = mid // n, col = mid % n. Read value = matrix[row][col].
  5. If value equals the target, return true. If it’s smaller, lo = mid + 1. If bigger, hi = mid − 1.
  6. 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

matrix (rows × columns)
0123
0
1
3
5
7
1
10
11
16
20
2
23
30
34
60
index mapping
n (columns)
4
mid
—
row
—
col
—
value
—
target
3
result
—
the same numbers, read row by row (position = row × n + col)
  1. 10
  2. 31
  3. 52
  4. 73
  5. 104
  6. 115
  7. 166
  8. 207
  9. 238
  10. 309
  11. 3410
  12. 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.

Step 1 / 17

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;}

The code, line by line

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 False

JavaScript 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 of class Solution in Python.)
  • Lines 2–3: m = how many rows, n = how many items per row. The problem promises at least one row and one column, so matrix[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 before mid holds n items, so dividing by n (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 row mid is.
  • 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.

Dry run

The 3 × 4 example (n = 4) with target = 3:

lohimidrow = mid // 4col = mid % 4valuenext
0115111111 > 3: hi = 4
0420255 > 3: hi = 1
0100011 < 3: lo = 1
1110133 = 3: return true
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

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.

Complexity

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.

Common mistakes and edge cases

What to say out loud, in this order:

  1. “Rows are sorted, and each row starts after the previous one ends, so reading row by row gives one sorted list.”
  2. “I can binary search that list without building it: position k is matrix[k // n][k % n].”
  3. Mention the alternative: “binary search to pick the row, then binary search inside the row. Same O(log(m × n)), but two loops.”
  4. Cost: O(log(m × n)) time, O(1) space.
  5. Dry-run the mapping for one mid so 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.