The problem
An m × n matrix has every row sorted left to right, and the first number of each row is larger than the last number of the row above.
Given a target, return true if it is in the matrix. It must run in O(log(m × n)) time.
Examples
01
- Input
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
- Output
true
02
- Input
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13
- Output
false
Constraints
- 1 ≤ m, n ≤ 100
- −10⁴ ≤ matrix[i][j], target ≤ 10⁴
The idea
Read row by row, the matrix is one sorted list of m × n numbers. So binary search that list without building it.
Position k in the list is row k ÷ n (rounded down) and column k mod n (the remainder). Binary search over k from 0 to m × n − 1, turning each mid into a row and column to read.
- Time
- O(log(m × n))
- Space
- O(1)
Solution · every language run against every case
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: rows, cols = len(matrix), len(matrix[0]) lo, hi = 0, rows * cols - 1 # the matrix, read row by row, is one sorted list while lo <= hi: mid = (lo + hi) // 2 v = matrix[mid // cols][mid % cols] # position k is row k // cols, column k % cols if v == target: return True if v < target: lo = mid + 1 else: hi = mid - 1 return False