Search a 2D Matrix
Problem Statement
You are given an m x n
2-D integer array matrix
and an integer target
.
- Each row in
matrix
is sorted in non-decreasing order. - The first integer of every row is greater than the last integer of the previous row.
Return true
if target
exists within matrix
or false
otherwise.
Can you write a solution that runs in O(log(m * n))
time?
Example 1:
Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10
Output: true
Example 2:
Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15
Output: false
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10000 <= matrix[i][j], target <= 10000
You should aim for a solution with O(log(m * n))
time and O(1)
space, where m
is the number of rows and n
is the number of columns in the matrix.
Recommended Time and Space Complexity
You should aim for a solution with O(log(m * n))
time and O(1)
space, where m
is the number of rows and n
is the number of columns in the matrix.
Hint 1
A brute force solution would be to do a linear search on the matrix. This would be an O(m * n)
solution. Can you think of a better way? Maybe an efficient searching algorithm, as the given matrix is sorted.
Hint 2
We can use binary search, which is particularly effective when we visualize a row as a range of numbers, [x, y]
where x
is the first cell and y
is the last cell of a row. Using this representation, it becomes straightforward to check if the target value falls within the range. How can you use binary search to solve the problem?
Hint 3
We perform a binary search on the rows to identify the row in which the target value might fall. This operation takes O(logm)
time, where m
is the number of rows. Now, when we find the potential row, can you find the best way to search the target in that row? The sorted nature of each row is the hint.
Hint 4
Once we identify the potential row where the target might exist, we can perform a binary search on that row which acts as a one dimensional array. It takes O(logn)
time, where n
is the number of columns in the row.
Solution
Brute Force
def search_matrix(matrix: List[List[int]], target: int) -> bool: for r in range(len(matrix)): for c in range(len(matrix[0])): if matrix[r][c] == target: return True return False
Time complexity: O(m * n)
Space complexity: O(1)
Staircase Search
def search_matrix(matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) r, c = 0, n - 1
while r < m and c >= 0: if matrix[r][c] > target: c -= 1 elif matrix[r][c] < target: r += 1 else: return True return False
Time complexity: O(m + n)
Space complexity: O(1)
Binary Search
def search_matrix(matrix: List[List[int]], target: int) -> bool: rows, cols = len(matrix), len(matrix[0])
top, bot = 0, rows - 1 while top <= bot: row = (top + bot) // 2 if target > matrix[row][-1]: top = row + 1 elif target < matrix[row][0]: bot = row - 1 else: break
if not (top <= bot): return False row = (top + bot) // 2 l, r = 0, cols - 1 while l <= r: m = (l + r) // 2 if target > matrix[row][m]: l = m + 1 elif target < matrix[row][m]: r = m - 1 else: return True return False
Time complexity: O(log m + log n)
Space complexity: O(1)
Binary Search (One Pass)
def search_matrix(matrix: List[List[int]], target: int) -> bool: rows, cols = len(matrix), len(matrix[0])
l, r = 0, rows * cols - 1 while l <= r: m = l + (r - l) // 2 row, col = m // cols, m % cols if target > matrix[row][col]: l = m + 1 elif target < matrix[row][col]: r = m - 1 else: return True return False
Time complexity: O(log(m * n))
Space complexity: O(1)