Search a 2D Matrix
You're given an m x n integer matrix with two properties: each row is sorted in non-decreasing order from left to right, and the first value of each row is greater than the last value of the row before it. Given an integer target, return true if target appears anywhere in the matrix and false otherwise. Your solution must run in O(log(m * n)) time, so scanning every cell is too slow.
Examples
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 returns true
3 is in row 0, column 1.
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 returns false
13 would belong in row 1 between 11 and 16, but no cell holds it.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -10^4 <= matrix[i][j], target <= 10^4
Hints
Every row ends below where the next one starts. What does the whole matrix look like if you read it row by row?
Treat the matrix as one sorted array of length m * n and binary search it, converting each flat index into a row and a column.
Set lo = 0 and hi = m * n - 1. While lo <= hi, take mid and read matrix[mid / n][mid % n]. Return true on a match, set lo = mid + 1 if the value is smaller than target, else hi = mid - 1. Return false after the loop.
Drill This: Your Approach First
Approach
The two properties mean that reading the rows one after another gives a single sorted list of m * n values. Binary search the flat indices 0 to m * n - 1, mapping each mid to the cell (mid / n, mid % n) where n is the number of columns, and halve the range exactly as in a 1D search. No row is ever copied or flattened.
Time
O(log(m * n))
Space
O(1)
Pitfall
Solutions
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int lo = 0, hi = m * n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int value = matrix[mid / n][mid % n];
if (value == target) {
return true;
} else if (value < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return false;
}
}from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // n][mid % n]
if value == target:
return True
elif value < target:
lo = mid + 1
else:
hi = mid - 1
return False