Search a 2D Matrix

Problem

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

Each row is sorted in non-decreasing order.
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 matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

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

Solution

Approach: Treat as 1D Array with Binary Search

The key insight is that the matrix properties (sorted rows, each row starts greater than previous row ends) make it equivalent to a sorted 1D array. We can use binary search by mapping 1D indices to 2D coordinates.

Mapping:

1D index to 2D: row = index // n, col = index % n
Total elements: m * n

Implementation

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        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
            # Convert 1D index to 2D coordinates
            row, col = mid // n, mid % n
            mid_value = matrix[row][col]

            if mid_value == target:
                return True
            elif mid_value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

Alternative (Two Binary Searches):

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False

        m, n = len(matrix), len(matrix[0])

        # First binary search: find the row
        top, bottom = 0, m - 1
        while top <= bottom:
            row = (top + bottom) // 2
            if target < matrix[row][0]:
                bottom = row - 1
            elif target > matrix[row][-1]:
                top = row + 1
            else:
                break

        # If no valid row found
        if not (top <= bottom):
            return False

        # Second binary search: search within the row
        row = (top + bottom) // 2
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

Complexity Analysis

Time Complexity: O(log(m * n)), which simplifies to O(log m + log n). We perform binary search over all elements.
Space Complexity: O(1), we only use a constant amount of extra space.

Key Insights

Virtual 1D Array: The matrix structure allows us to treat it as a sorted 1D array without actually flattening it. The index mapping preserves the sorted order.
Index Conversion: Converting between 1D and 2D indices: row = index // n, col = index % n where n is the number of columns.
Two Binary Search Approach: We can also do two separate binary searches: first to find the correct row, then to search within that row. Both approaches achieve the same time complexity.
Row Boundaries: In the two-search approach, a target belongs to a row if it’s between that row’s first and last elements: matrix[row][0] <= target <= matrix[row][-1].
Logarithmic Requirement: The O(log(m * n)) requirement rules out approaches that iterate through rows linearly, even with binary search within rows.