algoadvance

Write an efficient algorithm to search for a value in an m x n matrix. This matrix has the following properties:

Given a matrix and a target value, return true if the target is found in the matrix, and false otherwise.

Example:

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 3
Output: true

Input: matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 13
Output: false

Clarifying Questions

  1. Can the matrix be empty or have empty rows?
  2. Are there any constraints on the size of the matrix?
  3. Should we consider only integers, or can there be other types?

Strategy

Given the properties of the matrix, it can be viewed as a sorted 1D array. We can thus use binary search to efficiently search for the target. The general strategy is as follows:

  1. Compute the total number of elements in the matrix, which is m * n.
  2. Apply binary search on this range:
    • Convert the mid index of the 1D array to a corresponding position in the 2D matrix.
    • If the middle element matches the target, return True.
    • If the middle element is greater than the target, narrow the search to the left half.
    • If the middle element is less than the target, narrow the search to the right half.
  3. If the search completes without finding the target, return False.

Code

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    
    while left <= right:
        mid = (left + right) // 2
        mid_value = matrix[mid // n][mid % n]
        
        if mid_value == target:
            return True
        elif mid_value < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return False

# Example usage:
matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]
target = 3
print(searchMatrix(matrix, target))  # Output: True

target = 13
print(searchMatrix(matrix, target))  # Output: False

Time Complexity

The time complexity of the solution is O(log(m * n)) where m is the number of rows and n is the number of columns. This is because we are performing a binary search on m * n elements.

This approach ensures that the search is efficient even for large matrices.

Try our interview co-pilot at AlgoAdvance.com