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:

1. 
   Start from the top-right corner of the matrix.


2. 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.
  
  
  
  
  1. 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 < 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.