Search a 2D Matrix

Medium#74find a number

You get a matrix where each row is sorted and each row starts with a number bigger than the last number of the row above. Say whether a target number is in it, in O(log(rows · cols)) time. Our example: the 3 × 4 matrix below and 26 — the answer is true.

74 Search a 2D MatrixWalkthrough · 1×

Example: Rows [2, 4, 7, 9], [12, 15, 18, 20], [23, 26, 30, 34], find 26. On top, the same numbers read row after row as one list of 12.

0214273941251561872082392610301134012302479112151820223263034
still in the rangemiddle, checked nowthrown awayfound

4 numbers in a row: cols = 4

01/26
restart · back · play · step
Speed
1function searchMatrix(matrix, target):
2 cols = len(matrix[0])
3 lo = 0
4 hi = len(matrix) * cols - 1
5 while lo <= hi:
6 mid = floor((lo + hi) / 2)
7 value = matrix[floor(mid / cols)][mid mod cols]
8 if value == target:
9 return true
10 if value < target:
11 lo = mid + 1
12 else:
13 hi = mid - 1
14 return false
state
cols
4
lo
–
hi
–
mid
–
value
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Each row is sorted and starts above the end of the row before it, so the rows read one after another form one sorted list of rows · cols numbers.
  2. Binary search runs over that list’s indices without building it: index k is row floor(k / cols), column k mod cols. Here mid = 8 lands on 23, the first number of row 2.
  3. One search over all cells takes about log(rows · cols) steps, the same as finding the row first and then searching inside it.

Complexity

Time O(log(m · n)) for m rows and n columns: every step halves the range of cells. Memory O(1): the matrix is never copied into a list.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.