Search in Sorted Matrix
This algorithm efficiently searches for a target element in a sorted matrix by utilizing the sorted nature of the matrix.
The tip to this solution is the fact that every row/column is sorted in ascending order.
# Time O(n+m) | space O(1)
def searchInSortedMatrix(matrix, target):
row =0
col =len(matrix[0])-1
while row < len(matrix) and col >= 0:
if matrix[row][col] > target:
col -=1
elif matrix[row][col] < target:
row +=1
else:
return [row, col]
return [-1, -1]
matrix =[
[1,4,7,12,15,1000 ],
[2,5,19,31,32,1001 ],
[3,8,24,33,35,1002 ],
[40,41,42,44,45,1003 ],
[99,100,103,106,128,1004 ]
]
print(f" search in a sorted matrix:: {searchInSortedMatrix(matrix, 44)}")
By starting at the top-right corner and making decisions based on comparisons with the target, it optimally narrows down the search space until the target is found or determined to be absent.
Algorithm Walkthrough
Below is a step-by-step explanation of the implementation process of this algorithm.
Initialization
The algorithm initializes two pointers, row, and col, which are used to navigate the matrix.
row starts at the first row (0), and col starts at the last column (len(matrix[0]) - 1).
Search Loop
The algorithm enters a loop that continues as long as the row is within the bounds of the matrix (from 0 to len(matrix) - 1) and col is greater than or equal to 0.
Comparison with Target
Inside the loop, it compares the element at the current position matrix[row][col] with the target value.
If the element is greater than the target, it means the target might be located in a previous column, so it decrements col by 1 to move to the left.
If the element is less than the target, it means the target might be located in a subsequent row, so it increments the row by 1 to move down.
If the element is equal to the target, it means the target has been found, and the function returns the indices [row, col].
End of Loop
If the loop finishes without finding the target (i.e., row exceeds the last row or col becomes less than 0), it means the target is not present in the matrix. In this case, the function returns [-1, -1].
Time Analysis Complexity
The time complexity of this algorithm is O(m + n), where m is the number of rows and n is the number of columns in the matrix.
Since the algorithm starts at the top-right corner of the matrix and moves either left or down in each step, it traverses at most m + n elements before finding the target or determining that the target is not present.
Space Analysis Complexity
The space complexity of this algorithm is O(1), as it uses only a constant amount of additional space regardless of the size of the input matrix.