Search a 2D Matrix

Problem

https://leetcode.com/problems/search-a-2d-matrix/

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:sup:`4`<= matrix[i][j], target <= 10:sup:`4`

Pattern

Array, Binary Search, Matrix

Approaches

Binary Search

Explanation

The matrix is sorted such that we can treat it as a sorted 1D array. We can perform binary search on the matrix by mapping the 1D index to a 2D index using row = index // n and col = index % n.

Code

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    """Determine whether ``target`` is in ``matrix``."""
    m = len(matrix)
    n = len(matrix[0])

    left = 0
    right = m * n - 1
    while left <= right:
        mid = (left + right) // 2

        rows = mid // n
        cols = mid % n

        if matrix[rows][cols] == target:
            return True
        elif matrix[rows][cols] > target:
            right = mid - 1
        else:
            left = mid + 1

    return False

Test

>>> from search_a_2d_matrix__binary_search import searchMatrix
>>> searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3)
True
>>> searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13)
False

Complexity

Measure	Complexity	Notes
Time	\(O(\log(mn))\)	binary search on the matrix as if it were a 1D array
Auxiliary Space	\(O(1)\)

search_a_2d_matrix__binary_search.searchMatrix(matrix: list[list[int]], target: int) → bool

Determine whether target is in matrix.