Search a 2D Matrix

Start at the top-right corner. If the current value is bigger than the target, the whole column below it is also too big (columns are sorted), so move left. If it is smaller, the whole row to the left is too small, so move down. This staircase walk touches each row and column at most once, but it never uses the fact that the rows are laid out end-to-end into one giant sorted sequence — which is exactly what lets us do better.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        row, col = 0, len(matrix[0]) - 1
        while row < len(matrix) and col >= 0:
            val = matrix[row][col]
            if val == target:
                return True
            elif val > target:
                col -= 1
            else:
                row += 1
        return False

Because the last element of every row is smaller than the first element of the next row, the matrix is really just a sorted 1D array of m * n elements split into rows of length n. We can binary search over the flattened indices 0 .. m*n - 1 directly, without ever building the flattened array: a flat index mid maps to matrix[mid // n][mid % n].

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        lo, hi = 0, m * n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = matrix[mid // n][mid % n]
            if val == target:
                return True
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return False

Tracing matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13:

Why it’s correct: the two given properties are exactly what is needed to guarantee that reading the matrix row by row produces a fully sorted sequence, so mapping flat index i to matrix[i // n][i % n] reproduces ordinary binary search over that sequence. Complexity: the search window over m * n elements halves every step, giving O(log(m * n)) time, O(1) space.