Search a 2D Matrix
Task example: Search a 2D Matrix
Given a non-empty rectangular integer matrix, return True if target appears and False otherwise. Each row is sorted in non-decreasing order, and the first value of each row is greater than the last value of the previous row. Keep the matrix unchanged. The required runtime is O(log(m * n)); the linear scan is a baseline.
Rows and columns start at index zero. In the example, 3 is at row 0, column 1. Sorted rows alone are not enough: the ordering must continue across row boundaries.
Linear scan: video explanation
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 → True
Prefer reading? Follow the steps below.
- Visit each row with the outer loop, then each column with the inner loop. Compare matrix[row][col] with target.
- Return True immediately on a match. For target 3, check 1, then 3 at row 0, column 1. Stop without visiting the remaining cells.
- Return False only after both loops finish. For target 13, all 12 cells are checked and none matches.
Time complexity · O(m * n)
With m rows and n columns, a missing target requires m * n comparisons in the worst case: O(m * n).
Space complexity · O(1)
Only row and column indices are stored. No copy of the matrix is created: O(1) extra space.
Binary search: video explanation
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 → True
Prefer reading? Follow the steps below.
- Treat the row-by-row order as virtual indices from 0 to m * n - 1. Set left and right to these boundaries; do not create a flattened array.
- Find mid. Convert it to row = mid // cols and col = mid % cols. For four columns, index 5 maps to row 1, column 1: value 11.
- If the cell equals target, return True. If smaller, move left to mid + 1. If larger, move right to mid - 1. For target 3, the checked values are 11, 5, 1, then 3.
- When left passes right, return False. For target 13, check 11, 23, and 16; the remaining range becomes empty.
Unlike the linear scan, binary search uses the ordering to discard about half the remaining cells after each comparison. Divide by the number of columns, not rows.
Time complexity · O(log(m * n))
Each comparison roughly halves the range of m * n cells: O(log(m * n)) time.
Space complexity · O(1)
Only a few indices and one cell value are stored. Virtual indexing creates no new array: O(1) extra space.