LeetCode Solutions Blog

Search a 2D Matrix

Number: 74

Difficulty: Medium

Paid? No

Problem Description

Given an m x n matrix with each row sorted and the first element of each row larger than the last element of the previous row, determine if a given target integer exists in the matrix. The solution must run in O(log(m * n)) time.

Key Insights

The matrix is essentially a flattened sorted array due to its properties.
Use binary search to efficiently determine if the target exists.
Map the 1D binary search index to the corresponding 2D matrix coordinates using division and modulus operations.
Achieve O(log(m*n)) time complexity by navigating the matrix as if it were a single sorted list.

Space and Time Complexity

Time Complexity: O(log(m * n)) Space Complexity: O(1)

Solution

We can treat the matrix as a flattened sorted list without physically copying the elements. Given the total number of elements = m * n, perform binary search on indices ranging from 0 to (m*n - 1). For any index mid, calculate its corresponding row as mid // n and column as mid % n. Compare the element at matrix[row][col] with the target. If it equals target, return true; if it is less than target, search the right half; otherwise, search the left half.

Code Solutions

def searchMatrix(matrix, target):
    # Get number of rows and columns
    if not matrix or not matrix[0]:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    # Perform binary search over the virtual flattened array
    while left <= right:
        # Find the middle index
        mid = (left + right) // 2
        # Map the middle index to row and column in the matrix
        row = mid // cols
        col = mid % cols
        mid_value = matrix[row][col]

        # Check if the mid_value equals the target
        if mid_value == target:
            return True
        elif mid_value < target:
            left = mid + 1  # Move to the right subarray
        else:
            right = mid - 1  # Move to the left subarray
            
    # Target not found
    return False

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