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

To put this in plain English: you are given a rectangular grid of numbers. If you were to flatten this grid into a single list by placing each row end-to-end, the resulting list would be strictly increasing. You need to determine if a specific number (target) exists anywhere in this grid.

Constraints to Keep in Mind:

• m == matrix.length, n == matrix[i].length
• 1 <= m, n <= 100 (The matrix is at least 1x1, up to 100x100)
• -10^4 <= matrix[i][j], target <= 10^4

The Brute Force Approach

The most naive way to solve this is to simply check every single cell in the matrix using nested for loops.

• How it works: You iterate through row 0 from left to right, then row 1, and so on, comparing each element to the target.
• Why it's too slow: While simple, this ignores the sorted nature of the matrix entirely. It takes O(m \cdot n) time. In a 100x100 matrix, you might do up to 10,000 checks. We want to take advantage of the sorting to skip checking the vast majority of these numbers, getting our checks down to around 14 (since \log_2(10000) \approx 14).

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.

Think of it like this (ELI5): Imagine a long line of 12 people holding numbered tickets (sorted 1 to 12). If you tell them to form 3 rows of 4 people, the 6th person in the original line will be in the second row, second position. Why? Because the first 4 people filled the first row. 6 / 4 = 1 (meaning 1 full row is skipped), and the remainder 6 % 4 = 2 (meaning they are the 2nd person in the current row). We're just mathematically transforming a 1D position into 2D coordinates.

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;
}

Code Walkthrough

1. rows, cols = len(matrix), len(matrix[0]): We first grab the dimensions of the grid. We know it's at least 1x1, so matrix[0] won't crash.
2. low, high = 0, rows * cols - 1: We imagine the 2D grid as a 1D array. If the grid is 3x4, there are 12 items, meaning the virtual indices go from 0 to 11.
3. while low <= high:: Standard binary search loop. We keep searching as long as our search window is valid.
4. mid = low + (high - low) // 2: We pick the middle index of our current search window.
5. value = matrix[mid // cols][mid % cols]: The magic step. We convert the 1D mid index back into a 2D (row, col) pair to see what number actually lives there.
6. The rest is standard binary search: if we found the target, return True. If value < target, the target must be in the right half of our virtual array, so we move low. Otherwise, move high.

Hand Trace

Let's trace matrix = [[1, 3], [10, 11]], target = 3

• rows = 2, cols = 2. Total items = 4.
• low = 0, high = 3

Step	low	high	mid	mid // cols (row)	mid % cols (col)	value	Action
1	0	3	1	1 // 2 = 0	1 % 2 = 1	matrix[0][1] = 3	3 == 3, Return True

What if target = 5?

• Step 1: mid = 1, value = 3. 3 < 5, so low = mid + 1 = 2.
• Step 2: low = 2, high = 3. mid = 2. row = 2//2 = 1, col = 2%2 = 0. matrix[1][0] = 10.
• Step 3: 10 > 5, so high = mid - 1 = 1.
• Step 4: Loop condition low <= high (2 <= 1) breaks. 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

• Time Complexity: O(\log(m \cdot n)). In the worst case, binary search halves the search space at every step. Our initial search space is m \cdot n elements, so we do at most \log_2(m \cdot n) iterations. Each iteration requires O(1) constant time arithmetic to find the row and column.
• Space Complexity: O(1). We are only storing a few integer pointers (rows, cols, low, high, mid), which takes constant extra memory regardless of how large the matrix is. We do not actually flatten the matrix.

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.