74. Search a 2D Matrix

Problem Link

The key idea is to treat the 2D matrix as a 1D array, which reduces the problem to a classic binary search. This conceptual flattening is illustrated on the right. Once flattened, we map an index \(k\) in the 1D array back to its corresponding \((row,col)\) position in the matrix.

For a matrix of dimensions \(m\times n\), the mapping from index \(k\) to \((row,col)\) is:

• \(row=floor(k\div n)\), since each row contains \(n\) elements.
• \(col=k\mod n\), which gives the position within the current row after accounting for complete rows.

Runtime Complexity

Time: \(O(logn(mn))\), Total search space is \(mn\), which we're reducing by half in each iteration

Space: \(O(1)\), constant variables

PythonGo

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        l, r = 0, len(matrix)*len(matrix[0])
        mid = 0
        while l < r:
            mid = l + (r-l)//2
            if matrix[mid//n][mid%n] >= target:
                r = mid
            else:
                l = mid + 1

        if l < m*n and matrix[l//n][l%n] == target:
            return True
        return False

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    l, r := 0, m*n
    var mid int
    for l < r {
        mid = l + (r-l)/2
        if matrix[mid/n][mid%n] >= target {
            r = mid
        } else {
            l = mid + 1
        }
    }
    if l < m*n && matrix[l/n][l%n] == target {
        return true
    }
    return false
}

---