Sponsored
Sponsored
This approach begins searching from the top-right corner of the matrix. If the current element is equal to the target, return true. If the current element is greater than the target, move left. If the current element is less than the target, move down. This method effectively narrows down the search space, taking advantage of the sorted property of the matrix.
Time Complexity: O(m + n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), as no extra space is used.
1def searchMatrix(matrix, target):
2 row, col = 0, len(matrix[0]) - 1
3 while row < len(matrix) and col >= 0:
4 if matrix[row][col] == target:
5 return True
6 elif matrix[row][col] > target:
7 col -= 1
8 else:
9 row += 1
10 return FalseThe Python implementation makes use of similar logic as other language solutions, taking advantage of Python's simplicity and dynamic typing to efficiently track indices and compare values.
This approach uses binary search on each row of the matrix. Since each row is sorted, binary search can efficiently determine if the target exists within the row. If found in any row, the function returns true.
Time Complexity: O(m * log(n)), where m is the number of rows and n is the number of columns.
Space Complexity: O(1).
1public class Solution {
private bool BinarySearch(int[] array, int target) {
int left = 0, right = array.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) return true;
else if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
public bool SearchMatrix(int[][] matrix, int target) {
foreach (var row in matrix) {
if (BinarySearch(row, target)) return true;
}
return false;
}
}C# implementation employs a helper method `BinarySearch` to manage orderly checking of each row for the target using binary search. It utilizes C#'s syntax for array manipulation and traversal.