4.11.2 — Search a 2D Matrix

LeetCode 74 · Medium

The problem

Each row of the matrix is sorted left to right, and the first value of each row is greater than the last value of the row above. Return true if target is present. Must be O(\log(m \cdot n)).

[[ 1,  3,  5,  7],
 [10, 11, 16, 20],
 [23, 30, 34, 60]]

target = 3   →  true
target = 13  →  false

The pattern

Read the second condition again: every row starts above where the previous row ended. So if you read the matrix row by row, the numbers come out in fully sorted order.

It is a sorted array that happens to be stored in rows.

So run an ordinary binary search over the range 0 … m·n − 1, and convert each virtual index back into a row and a column when you need to read a value:

\text{row} = \left\lfloor \frac{\text{index}}{\text{cols}} \right\rfloor \qquad \text{col} = \text{index} \bmod \text{cols}

Integer division gives the row because each row holds exactly cols items; the remainder gives the position within it. This is the row-major formula from 4.2, the same arithmetic that lays a 2-D array out in flat memory, and the reverse of the box-index formula in 4.4.8.

The solution

Python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        low, high = 0, rows * cols - 1

        while low <= high:
            mid = low + (high - low) // 2
            value = matrix[mid // cols][mid % cols]      # virtual index → cell

            if value == target:
                return True
            if value < target:
                low = mid + 1
            else:
                high = mid - 1

        return False

TypeScript

function searchMatrix(matrix: number[][], target: number): boolean {
  const rows = matrix.length, cols = matrix[0].length;
  let low = 0, high = rows * cols - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    const value = matrix[Math.floor(mid / cols)][mid % cols];

    if (value === target) return true;
    if (value < target) low = mid + 1;
    else high = mid - 1;
  }

  return false;
}

Note that cols is the divisor, not rows. Getting that backwards is the only real trap, and it happens to everyone once. Check it on a corner: with 4 columns, virtual index 5 should be row 1, column 1. 5 // 4 = 1 ✓, 5 % 4 = 1 ✓.

Complexity

O(\log(m \cdot n)) time, O(1) space.

Note that \log(mn) = \log m + \log n, so this is exactly the same cost as doing two nested binary searches — one to find the row, one to find the column within it. The single search is not faster, it is just less code.

The two-pass version

# find the row whose range contains the target, then search within it
top, bottom = 0, rows - 1
while top <= bottom:
    r = (top + bottom) // 2
    if target > matrix[r][-1]: top = r + 1
    elif target < matrix[r][0]: bottom = r - 1
    else: break
else:
    return False
# then a plain binary search on matrix[r]

Same complexity, more code. It has one genuine advantage worth knowing: if the rows are stored separately in memory rather than as one contiguous block, the two-pass version touches fewer cache lines, because it settles on a row and then stays inside it. That matters in a real system, not on a coding judge.

The other version of this problem

Search a 2D Matrix II (LeetCode 240) looks almost identical but is a different problem. There, rows and columns are each sorted, but a row does not have to start after the previous row ends. So the flattened array is not sorted, and binary search over virtual indices is wrong.

The answer there is a staircase walk: start at the top-right corner. If the value is too large, move left, because everything below in that column is even larger. If too small, move down. Each step eliminates a whole row or column, so it is O(m + n).

Being able to tell these two problems apart, and to say which condition separates them, is more valuable than either solution.

What the interviewer will push on

"Why can you treat this as one array?" Because each row starts above where the previous ended, so reading row by row gives sorted order.

"Which is the divisor?" The number of columns.

"Is O(\log(mn)) better than two binary searches?" No — they are equal, since \log(mn) = \log m + \log n. Say this; it shows you can read the arithmetic rather than assume one number is smaller.

"What if rows were sorted but did not chain together?" That is Matrix II. Staircase from the top-right corner, O(m + n).

One thing to volunteer: verify the index formula on a corner out loud before running. It costs three seconds and it is the only thing here that can be wrong.

Next: 4.11.3 Koko Eating Bananas — the first problem where there is no sorted array at all, and you binary search the answer instead.