Searching a 2D Matrix

Problem Statement:

You are given an m x n integer matrix matrix with the following properties:

1. Each row is sorted in non-decreasing order.
2. The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in the matrix or false otherwise.

You must write a solution with a time complexity of O(log(m × n)).

Examples:

Example 1:

Input:

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

Output:

true

Example 2:

Input:

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

Output:

false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

Approach:

To achieve the required time complexity of O(log(m × n)), treat the matrix as a flattened sorted array and use binary search.

Key Observations:

1. Matrix to 1D Mapping:
   • Each element in the 2D matrix can be mapped to a 1D array index using:
     • Row: index // n
     • Column: index % n
2. Binary search can be performed directly on this virtual 1D array.

Implementation:

# Function to search the target in a 2D matrix
def searchMatrix(matrix, target):
    # Edge case: empty matrix
    if not matrix:
        return False

    # Dimensions of the matrix
    m, n = len(matrix), len(matrix[0])

    # Binary search boundaries
    left, right = 0, m * n - 1

    while left <= right:
        mid = (left + right) // 2
        # Convert mid index to 2D matrix coordinates
        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
result = searchMatrix(matrix, target)
print(result)  # Output: True

Explanation:

1. Initialization:

   • left is set to 0 (start of the virtual array).
   • right is set to m × n - 1 (end of the virtual array).

2. Binary Search:

   • Calculate the middle index: mid = (left + right) // 2.
   • Convert the middle index to matrix coordinates using:
     • Row: mid // n
     • Column: mid % n
   • Compare mid_value (element at matrix[row][col]) with target.
     • If equal, return True.
     • If less, move left pointer to mid + 1.
     • If greater, move right pointer to mid - 1.

3. End Condition:

   • If left > right, the target is not in the matrix; return False.

Complexity Analysis:

• Time Complexity:
  • Binary search runs in O(log(m × n)) because the virtual array has m × n elements.
• Space Complexity:
  • O(1) since no additional space is used.