Finding the Row Containing a Target in a Sorted Matrix in Python
In this problem, you're given a matrix of integers where each row and each column is sorted in ascending order. The goal is to find the index of the row that contains a specific target value. If the target value is not found in the matrix, return None. This is a common matrix problem that can be solved efficiently by taking advantage of the sorted structure. Instead of checking each cell (which would take O(n × m) time), you can reduce the complexity to O(n + m), where n is the number of rows and m is the number of columns. Problem Approach We make use of the matrix's properties—namely that values increase as we move right and down, and decrease as we move left and up. Steps: Start from the top-right corner of the matrix. Use a loop to traverse the matrix: If the current value equals the target, return the current row index. If the current value is greater than the target, move left. If the current value is less than the target, move down. If the loop completes without finding the target, return None. Python Implementation def find_row_with_target(matrix, target): if not matrix or not matrix[0]: return None # Matrix is empty n = len(matrix) # Number of rows m = len(matrix[0]) # Number of columns # Start at the top-right corner row, col = 0, m - 1 while row = 0: if matrix[row][col] == target: return row # Target found elif matrix[row][col] > target: col -= 1 # Move left else: row += 1 # Move down return None # Target not found Example Usage matrix = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ] print(find_row_with_target(matrix, 7)) # Output: 1 print(find_row_with_target(matrix, 13)) # Output: None Conclusion This solution demonstrates how understanding data structure properties can lead to more efficient algorithms. Instead of brute-force search, a directional approach through the matrix takes full advantage of the sorted nature, resulting in a linear time complexity relative to the dimensions of the matrix.
In this problem, you're given a matrix of integers where each row and each column is sorted in ascending order. The goal is to find the index of the row that contains a specific target value. If the target value is not found in the matrix, return None.
This is a common matrix problem that can be solved efficiently by taking advantage of the sorted structure. Instead of checking each cell (which would take O(n × m) time), you can reduce the complexity to O(n + m), where n is the number of rows and m is the number of columns.
Problem Approach
We make use of the matrix's properties—namely that values increase as we move right and down, and decrease as we move left and up.
Steps:
- Start from the top-right corner of the matrix.
- Use a loop to traverse the matrix:
- If the current value equals the target, return the current row index.
- If the current value is greater than the target, move left.
- If the current value is less than the target, move down.
- If the loop completes without finding the target, return
None.
- If the loop completes without finding the target, return
Python Implementation
def find_row_with_target(matrix, target):
if not matrix or not matrix[0]:
return None # Matrix is empty
n = len(matrix) # Number of rows
m = len(matrix[0]) # Number of columns
# Start at the top-right corner
row, col = 0, m - 1
while row < n and col >= 0:
if matrix[row][col] == target:
return row # Target found
elif matrix[row][col] > target:
col -= 1 # Move left
else:
row += 1 # Move down
return None # Target not found
Example Usage
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
print(find_row_with_target(matrix, 7)) # Output: 1
print(find_row_with_target(matrix, 13)) # Output: None
Conclusion
This solution demonstrates how understanding data structure properties can lead to more efficient algorithms. Instead of brute-force search, a directional approach through the matrix takes full advantage of the sorted nature, resulting in a linear time complexity relative to the dimensions of the matrix.
