Sponsored
Sponsored
The matrix can be viewed as a single sorted list. Hence, we can perform a binary search on the entire matrix by treating it as a 1D array. Suppose we have a matrix of size m x n, any element in the matrix can be accessed using a single index calculated as follows:
Element at index k can be accessed using matrix[k / n][k % n], where / and % represent integer division and modulus operations, respectively.
This approach ensures that the solution operates in O(log(m * n)) time complexity as required.
Time complexity: O(log(m * n))
Space complexity: O(1)
1class Solution:
2 def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3 if not matrix: return False
4 m, n = len(matrix), len(matrix[0])
5 left, right = 0, m * n - 1
6 while left <= right:
7 mid = left + (right - left) // 2
8 mid_val = matrix[mid // n][mid % n]
9 if mid_val == target:
10 return True
11 elif mid_val < target:
12 left = mid + 1
13 else:
14 right = mid - 1
15 return FalseThis Python solution uses Python's List data structure features with integer division to manage matrix accesses. It succinctly reflects the binary search approach for optimal time complexity.
The problem also allows for a two-step binary search owing to the special properties of the matrix. First, we identify the row which potentially contains the target by performing binary search on first elements of each row. Then, we conduct a binary search in that specific row.
Although not strictly O(log(m * n)), this approach exploits the matrix's properties in an efficient manner for similar effective results.
Time complexity: O(log(m) + log(n))
Space complexity: O(1)
1This C code expands the binary search to two distinct logical steps: first identifying the potential row and then binary searching within that row itself to find the target efficiently.