LeetCode 74 · Medium · Binary Search

Search a 2D Matrix

Given an m × n matrix whose rows are sorted and where each row starts above the previous row's end, return whether target is in it, in O(log(m·n)) time.

O(log mn)time
O(1)space
/ and %flat index → cell

rows split by ; or | (or paste [[1,3],[5,7]]) · up to 5×5 · −999 to 999 · sorted row by row, each row starting above the last · target: −9999 to 9999

matrix corner = flat index

flat index = row · cols + col

public boolean searchMatrix(int[][] matrix, int target) { int rows = matrix.length; int cols = matrix[0].length; int l = 0; int r = rows * cols - 1; while (l <= r) { int mid = l + (r - l) / 2; int row = mid / cols; int col = mid % cols; if (matrix[row][col] > target) { r = mid - 1; } else if (matrix[row][col] < target) { l = mid + 1; } else { return true; } } return false;}
l
—
r
—
mid
—
(row, col)
—
matrix[row][col]
—
r − l + 1
—

Why it works

  1. Brute force checks every cell: O(m·n). But each row is sorted and starts above the previous row's end, so the matrix read row by row is one sorted list of m·n values.
  2. Search that list without building it. Flat index i lives at row i / cols, column i % cols: i / cols full rows come before it (integer division), and i % cols is how far into its row it sits.
  3. Same template as 704: l <= r, mid ± 1. O(log(m·n)) = O(log m + log n) time, O(1) space.
  4. Pitfall: divide by cols, the row length, not rows. On a square matrix both work, so the bug hides until the matrix is not square.
  5. Alternative, two binary searches: first over the rows (is target between row[0] and row[cols - 1]?) to find the only row that could hold it, then a normal binary search inside that row. Same O(log m + log n), more code and more boundaries to get wrong.
  6. Follow-up, 240 Search a 2D Matrix II: rows and columns sorted separately, with no global order, so the flat trick fails. Start at the top-right corner and step left or down: O(m + n).