Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The matrix looks two-dimensional, but the key rule makes it behave like one long sorted array:

  • each row is sorted from left to right
  • the first value in a row is greater than the last value in the previous row

So the task is not really “search a grid.” It is “search a sorted sequence” while remembering that the sequence happens to be stored in matrix form.

That shift is the whole interview. Once that idea is clear, the rest becomes standard binary search.

The easiest way to derive the optimal solution

Start with the ordering guarantee between rows. If the last value of row r is smaller than the first value of row r + 1, then row boundaries do not break the sorted order.

That means the matrix entries, read in row-major order, are globally sorted:

matrix[0][0], matrix[0][1], ..., matrix[0][n - 1], matrix[1][0], ...

Now imagine giving every cell a one-dimensional index from 0 to rows * columns - 1.

If a flat index is called index, then:

  • row = index // columns
  • column = index % columns

So binary search works exactly as it would on a normal sorted array. The only extra step is converting the middle index back into a row and column before reading the value.

Best approach

Binary search over the virtual flattened array is the cleanest answer.

  • Time: O(log(m * n))
  • Extra space: O(1)

There is also a two-phase version:

  1. binary search to find the only row that could contain the target
  2. binary search inside that row

Its complexity is O(log m + log n), which is asymptotically the same. In practice, the flattened-array version is usually easier to explain and implement.

Python solution

from typing import List


def search_sorted_matrix(matrix: List[List[int]], target: int) -> bool:
    """Return True when target exists in a row-major globally sorted matrix."""
    if not matrix or not matrix[0]:
        return False

    row_count = len(matrix)
    column_count = len(matrix[0])
    left_index = 0
    right_index = row_count * column_count - 1

    while left_index <= right_index:
        middle_index = left_index + (right_index - left_index) // 2

        # Map the virtual one-dimensional index back to the matrix cell.
        row_index, column_index = divmod(middle_index, column_count)
        candidate_value = matrix[row_index][column_index]

        if candidate_value == target:
            return True

        if candidate_value < target:
            left_index = middle_index + 1
        else:
            right_index = middle_index - 1

    return False


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        return search_sorted_matrix(matrix=matrix, target=target)

This implementation keeps the logic small and direct. The only non-obvious step is the divmod conversion, which turns a virtual flat index back into the correct matrix cell.

Why this works

Binary search is valid only when the search space is sorted. This problem gives exactly that once the matrix is viewed in row-major order.

The row rule guarantees two things:

  1. values inside a row increase from left to right
  2. every value in row r + 1 is greater than every value in row r

Together, those facts mean the entire matrix is globally sorted if flattened row by row.

At each step, binary search compares the target against the middle value and safely discards half of the remaining cells:

  • if the middle value is too small, everything before it is also too small
  • if the middle value is too large, everything after it is also too large

Because the algorithm never throws away a region that could still contain the target, it is correct.

Interview follow-ups

What if the interviewer wants a two-step binary search instead?

That is still a strong answer. First, binary search over the rows using each row’s first and last values to find the only possible row. Then run a second binary search inside that row. The reasoning is simple: the target can belong to at most one row because row ranges do not overlap. This approach has time complexity O(log m + log n) and constant extra space. It is slightly longer to code than the flattened approach, but some interviewers find it more intuitive on the first pass.

What if the matrix is sorted left-to-right and top-to-bottom, but rows can overlap?

Then the flattening trick is no longer valid. A later row might start with a value smaller than some value in an earlier row, so the global row-major order disappears. In that version, a common optimal approach is to start at the top-right corner and move left when the current value is too large or down when it is too small. Each move removes one row or one column, so the runtime is O(m + n) with O(1) extra space. That is the core idea behind Search a 2D Matrix II.

How would you return the target’s position instead of a boolean?

The algorithm barely changes. Keep the same binary search over virtual indices, and when the target is found, return (row_index, column_index) instead of True. If the loop ends without a match, return a sentinel such as (-1, -1) or None, depending on the interface. The complexity stays the same because the search work is identical.

What if the matrix is extremely large and random memory access is expensive?

The big tradeoff becomes access pattern rather than asymptotic complexity. Binary search minimizes the number of comparisons, but it jumps around. If the data lives on disk or across the network, those jumps may be costly. In that situation, an interviewer may care more about storage layout, chunking, or whether the rows can be indexed separately. The algorithmic idea is still binary search, but the systems answer is that access cost can dominate the textbook O(log(m * n)) comparison count.