Search a 2D Matrix

medium LeetCode #74
array binary-search matrix

Description

You are given an m x n integer 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
Explanation: 3 is in the matrix at position [0][1].

Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Explanation: 13 is not in the matrix. It would fall between 11 and 16 in row 1.

Constraints

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

Complexity

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

Hints

Show Hints
Pattern
Binary search on virtual 1D array
Approach
Use binary search with index conversion: for index i in [0, m*n), row = i // n, col = i % n
Complexity
Treat the 2D matrix as a sorted 1D array of length m*n

Solutions

Show PY Solution 
def binary_search(arr: list[int], target: int) -> bool:
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        v = arr[mid]

        if v == target:
            return True

        if v < target:
            left = mid + 1
        else:
            right = mid - 1

    return False


def solution(matrix: list[list[int]], target: int) -> bool:
    nrows = len(matrix)
    ncols = len(matrix[0])
    for r in range(nrows):
        if binary_search(matrix[r], target):
            return True

    for c in range(ncols):
        cols = []
        for r in range(nrows):
            cols.append(matrix[r][c])
        if binary_search(cols, target):
            return True

    return False