Search a 2D Matrix

 

Problem Statement: Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

1. Clarify the problem:

  • Can the matrix be empty?
  • Can the target value be negative?

2. Analyze the problem:

  • Input: 2D matrix of integers (matrix), target value (target)
  • Output: Boolean indicating whether the target value is present in the matrix
  • Constraints:
    • The matrix can be empty.
    • The matrix is sorted row-wise and column-wise.
    • The target value can be any integer.

3. Design an algorithm:

  • Start from the top-right corner of the matrix.
  • Compare the current element with the target value:
    • If the current element is equal to the target value, return True.
    • If the current element is greater than the target value, move left.
    • If the current element is less than the target value, move down.
  • Repeat the above step until either the target value is found or we go out of bounds of the matrix.
  • If we go out of bounds, the target value is not present in the matrix. Return False.

4. Explain your approach:

  • We will start from the top-right corner of the matrix and traverse the matrix by moving left or down based on the comparison of the current element with the target value.
  • This approach takes advantage of the matrix's sorted nature to efficiently search for the target value.
  • If we find the target value during the traversal, we return True. If we go out of bounds without finding the target value, we return False.

5. Write clean and readable code:

python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        
        rows, cols = len(matrix), len(matrix[0])
        row, col = 0, cols - 1
        
        while row < rows and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1
            else:
                row += 1
        
        return False

6. Test your code: I will test the code with the following test cases:

  • Test case 1: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
  • Test case 2: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
  • Test case 3: matrix = [[]], target = 0
  • Test case 4: matrix = [], target = 5
python
solution = Solution()
print(solution.searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3))  # Expected output: True
print(solution.searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13))  # Expected output: False
print(solution.searchMatrix([[]], 0))  # Expected output: False
print(solution.searchMatrix([], 5))  # Expected output: False

7. Optimize if necessary: The provided algorithm is already quite efficient with a time complexity of O(m + n), where m is the number of rows and n is the number of columns in the matrix. It traverses at most m + n elements in the worst case.

8. Handle error cases: The code handles the following error cases:

  • If the matrix is empty (not matrix or not matrix[0]), it returns False.
  • If the target value is not found during the traversal, it returns False.

9. Discuss complexity analysis:

  • The time complexity of the algorithm is O(m + n) since we traverse at most m + n elements in the worst case.
  • The space complexity is O(1) since we only use a constant amount of additional space to store the indices and variables.
  • The algorithm efficiently searches the matrix by taking advantage of its sorted nature, resulting in a relatively low time complexity.
Next Post Previous Post