Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Search a 2D Matrix

LeetCode #74Medium
Treat the grid as one flat sorted array · binary search 0..m·n−1

Given an m x n matrix where each row is sorted left-to-right and the first integer of each row is greater than the last integer of the previous row, determine whether a target value exists in the matrix in O(log(m·n)) time.

Asked atAmazonMicrosoftGoogle
step 1 / 5
3 × 4 grid · read as a flat sorted array of length 12
1
3
5
7
10
11
16
20
23
30
34
60
Binary search the flattened grid
▸
1lo ← 0;  hi ← m·n − 1
2while lo <= hi:
3    mid ← lo + (hi − lo) / 2;  v ← grid[mid / n][mid % n]
4    if v == target: return true
5    else if v < target: lo ← mid + 1
6    else:               hi ← mid − 1
7return false
state
  • target3
  • grid3×4
  • flat length12
  • lo0
  • hi11

line 1Each row is sorted AND the first value of every row is larger than the last value of the row above. That means the whole 3×4 grid is one sorted array of length 12 — just folded into rows. So we binary-search the flat indices 0..11. To read index idx, map it back to the grid with row = idx / 4 and col = idx % 4. Start lo = 0, hi = 11.