Matrix · 135Medium
Search a 2D Matrix
Given an m x n matrix where each row is sorted ascending and the first value of each row is greater than the last value of the previous row, return true if target is present. Must run in O(log(m * n)) time.
Constraints
- m == matrix.length, n == matrix[i].length
- 1 <= m, n <= 100
- -10^4 <= matrix[i][j], target <= 10^4
Examples
searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3) -> true searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13) -> false searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 60) -> true // last cell searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 0) -> false // below all searchMatrix([[1]], 1) -> true // 1x1 searchMatrix([[1],[3],[5]], 4) -> false // single column
Edge cases
- A target smaller or larger than everything.
- A 1x1 matrix.
Show the target complexity (spoiler)
- Naive
- O(m * n) time — scan every cell, ignoring the sorted structure.
- Target
- O(log(m * n)) time — binary search the matrix as a flat array, mapping index i to (row = i / n, col = i % n).
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/16-matrix/135-search-a-2d-matrix.js ./practice c 135