Search a 2D Matrix medium

Problem Statement

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The 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.

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

Steps

The key to efficiently solving this problem is to leverage the sorted nature of the matrix. Instead of treating it as a 2D array, we can treat it as a sorted 1D array. This allows us to use binary search for a significantly faster solution than nested loops.

Here's the step-by-step approach:

1. Flatten the matrix (conceptually): Imagine the matrix as a single sorted array. The first row's elements come first, followed by the second row's elements, and so on.

2. Determine the size of the "flattened" array: The total number of elements is m * n, where m is the number of rows and n is the number of columns.

3. Apply Binary Search: Use binary search on this conceptually flattened array. The key is to adapt the index calculations to map the binary search's mid-point index back to the row and column indices in the original matrix.

4. Return the result: The binary search will return True if the target is found and False otherwise.

Explanation

The binary search algorithm efficiently searches a sorted array. By conceptually flattening the matrix, we maintain the sorted property, allowing us to use binary search. The crucial part is the mapping between the linear index used in the binary search and the row and column indices of the matrix.

The left and right pointers in the binary search define the search space within the "flattened" array. The mid index is calculated as the average of left and right. Then, we determine the row and col of the element at this mid index in the original matrix. If the matrix element at matrix[row][col] equals the target, we've found it! If it's less than the target, we adjust the left pointer; otherwise, we adjust the right pointer. This continues until the left pointer surpasses the right pointer.

Code

def searchMatrix(matrix, target):
    """
    Searches for a target value in a sorted 2D matrix using binary search.

    Args:
        matrix: A list of lists representing the 2D matrix.
        target: The integer value to search for.

    Returns:
        True if the target is found, False otherwise.
    """
    if not matrix or not matrix[0]:  # Handle empty matrix case
        return False

    rows = len(matrix)
    cols = len(matrix[0])
    left = 0
    right = rows * cols - 1

    while left <= right:
        mid = (left + right) // 2
        row = mid // cols
        col = mid % cols
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

Complexity

• Time Complexity: O(log(m*n)), where 'm' is the number of rows and 'n' is the number of columns. This is due to the binary search algorithm.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space. It operates in-place without creating large auxiliary data structures.