240_Search a 2D Matrix II
[Medium]
Write an efficient algorithm that searches for a value in an mxn matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
Example:
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5
, return true
.
Given target = 20
, return false
.
Solution:
Idea:
Start from top-right, check if the element equals to target.
If equal, return True.
If larger than target, move to the left.
If smaller than target, move to below.
Time Complexity: where m is the number of row, n is the number of column.
Space Complexity:
def searchMatrix(matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
# corner case when matrix is empty
if not matrix: return False
# start from top-right corner
i, j = 0, len(matrix[0]) - 1
# keep searching while there are unclassified rows and columns
while i < len(matrix) and j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
j -= 1
else:
# matrix[i][j] < target
i += 1
return False
Last updated
Was this helpful?